# Cod sursa(job #2176476)

Utilizator Data 17 martie 2018 15:17:19 Arbori de intervale 50 cpp done Arhiva educationala 1.18 kb
``````#include<iostream>
#include<algorithm>
#define NMAX 100010
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;
int m = (left + right) >> 1;
if (a <= m) rez = max(rez, query(a, b, nod<<1, left, m));
if (m < b) rez = max(rez, query(a, b, (nod<<1) + 1, m + 1, right));

return rez;
}

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

int N, M, x, y, op, i;
cin >> N >> M;
for (i = 1; i <= N; i++) {
cin >> x;
update(i, x, 1, 1, N);
}
for (i = 1; i <= M; i++) {
cin >> op >> x >> y;
if (op == 0) {
cout << query(x, y, 1, 1, N) << endl;
} else {
update(x, y, 1, 1, N);
}
}

return 0;
}
``````