# Cod sursa(job #1494035)

Utilizator Data 30 septembrie 2015 15:57:05 Arbori de intervale 100 cpp done Arhiva educationala 1.17 kb
``````#include <stdio.h>
#include <algorithm>

#define maxdim 100005

using namespace std;

int n, q;
int arb[4*maxdim];

void update(int nod, int st, int dr, int poz, int val) {
if (st == dr) {
arb[nod] = val;
return;
}

int mij = (st + dr) >> 1;
int nodst = nod << 1;
int noddr = nodst | 1;

if (poz <= mij) {
update(nodst, st, mij, poz, val);
} else {
update(noddr, mij+1, dr, poz, val);
}

arb[nod] = max(arb[nodst], arb[noddr]);
}

void query(int nod, int st, int dr, int a, int b, int &sol) {
if (a <= st && dr <= b) {
sol = max(sol, arb[nod]);
return;
}

int mij = (st + dr) >> 1;
int nodst = nod << 1;
int noddr = nodst | 1;

if (a <= mij) {
query(nodst, st, mij, a, b, sol);
}
if (b > mij) {
query(noddr, mij+1, dr, a, b, sol);
}
}

int main() {

freopen("arbint.in", "r", stdin);
freopen("arbint.out", "w", stdout);

scanf("%d %d", &n, &q);
for (int i = 1; i <= n; ++i) {
int x; scanf("%d", &x);
update(1, 1, n, i, x);
}

while (q--) {
int type, x, y;
scanf("%d %d %d", &type, &x, &y);

if (type == 0) {
int sol = 0;
query(1, 1, n, x, y, sol);
printf("%d\n", sol);
} else {
update(1, 1, n, x, y);
}
}

return 0;
}
``````