# Cod sursa(job #532616)

Utilizator Data 12 februarie 2011 01:37:06 Arbori de intervale 0 cpp done Arhiva educationala 2.23 kb
``````#include <iostream>
#include <cstdio>
#include <cmath>
#include <fstream>
#include <string>

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) {
if (from < 0 || to >= length) {
throw exception();
}
return get(0, 0, length, from, to);
}

void update(int position, int val) {
if (position >= length || position < 0) {
throw exception();
}
values[position] = val;
update(0, 0, length, position);
}

~Arb() {
delete arb;
}

};

int main() {
int n, m;

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

scanf("%d%d", &n, &m);
int *a = new int[m];
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
Arb arb = Arb(a, n);
/*
for (int i = 0; i < m; i++) {
int op, a, b;
scanf("%d%d%d", &op, &a, &b);
if (op == 0) {
printf("%d\n", arb.getMax(a-1, b-1));
} else if (op == 1) {
arb.update(a-1, b);
}
}
*/
return 0;
}
``````