# Cod sursa(job #2176479)

Utilizator Data 17 martie 2018 15:26:36 Arbori de intervale 100 cpp done Arhiva educationala 1.3 kb
``````#include<cstdio>
#define NMAX 100010
#define Max(a,b) a > b ? a : b
using namespace std;

int AINT[NMAX<<2];

void update(int pos, int val, int nod, int left, int right) {
if (left == right) {
AINT[nod] = val;
return;
}

int m = (left + right) >> 1;
if (pos <= m) update(pos, val, nod<<1, left, m);
else update(pos, val, (nod<<1) + 1, m + 1, right);

AINT[nod] = Max(AINT[nod<<1], AINT[(nod<<1) + 1]);
}

int query (int a, int b, int nod, int left, int right) {
if (a <= left && right <= b) {
return AINT[nod];
}

int rez = 0, tmp = 0;
int m = (left + right) >> 1;
if (a <= m) {
tmp = query(a, b, nod<<1, left, m);
rez = Max(rez, tmp);
}
if (m < b) {
tmp = query(a, b, (nod<<1) + 1, m + 1, right);
rez = Max(rez, tmp);
}

return rez;
}

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

int N, M, x, y, op, i;
scanf("%d %d", &N, &M);
for (i = 1; i <= N; i++) {
scanf("%d", &x);
update(i, x, 1, 1, N);
}
for (i = 1; i <= M; i++) {
scanf("%d %d %d", &op, &x, &y);
if (op == 0) {
printf("%d\n", query(x, y, 1, 1, N));
} else {
update(x, y, 1, 1, N);
}
}

return 0;
}
``````