# Cod sursa(job #532605)

Utilizator Data 12 februarie 2011 01:02:49 Arbori de intervale 0 cpp done Arhiva educationala 1.97 kb
``````#include <iostream>
#include <fstream>

using namespace std;

class Arb {
private:
int *arb;
int *values;
int length;

int update(int node, int l, int r, int position) {
int m = l+r >> 1;
if (r-l == 1) {
return arb[node] = values[l];
}
int candidate;
if (position < m) {
candidate = update(node*2+1, l, m, position);
return arb[node] = max(arb[node*2+2], candidate);
} else {
candidate = update(node*2+2, m, r, position);
return arb[node] = max(arb[node*2+1], candidate);
}
}

int get(int node, int l, int r, int from, int to) {
int m = l+r >> 1;
if (from <= l && r-1 <= to) {
return arb[node];
}
int candidate = INT_MIN;
if (to >= m) {
candidate = max(candidate, get(node*2+2, m, r, from, to));
}
if (from < m) {
candidate = max(candidate, get(node*2+1, l, m, from, to));
}
return candidate;
}

int build(int node, int l, int r) {
int m = l+r >> 1;
if (r-l == 1) {
return arb[node] = values[l];
}
return arb[node] = max(build(node*2+1, l, m),
build(node*2+2, m, r));
}

public:
Arb(int *aptr, int length) {
arb = new int[4*length];
values = aptr;
this->length = length;
build(0, 0, length);
}

int getMax(int from, int to) {
return get(0, 0, length, from, to);
}

void update(int position, int val) {
values[position] = val;
update(0, 0, length, position);
}

~Arb() {
delete arb;
}

};

int main() {
int n, m;
int *a = new int[m];

ifstream in("arbint.in");
ofstream out("arbint.out");

in >> n >> m;
for (int i = 0; i < n; i++) {
in >> a[i];
}
Arb arb = Arb(a, n);
for (int i = 0; i < m; i++) {
int op, a, b;
in >> op >> a >> b;
if (op == 0) {
out << arb.getMax(a-1, b-1) << endl;
} else if (op == 1) {
arb.update(a-1, b);
}
}
return 0;
}
``````