Voltar

## Árvore de segmentos - Estrutura de dados

0 Curtidas
```#include
#include
#include
#include
using namespace std;

class SegmentTree{
public:
vector arr, tree;
int n;

SegmentTree(){}
SegmentTree(const vector &arr) : arr(arr) {
initialize();
}

//must be called after assigning a new arr.
void initialize(){
n = arr.size();
tree.resize(4*n + 1);
initialize(0, 0, n-1);
}

int query(int query_left, int query_right) const{
return query(0, 0, n-1, query_left, query_right);
}

void update(int where, int what){
update(0, 0, n-1, where, what);
}

private:
int initialize(int node, int node_left, int node_right);
int query(int node, int node_left, int node_right, int query_left, int query_right) const;
void update(int node, int node_left, int node_right, int where, int what);
};

int SegmentTree::initialize(int node, int node_left, int node_right){
if (node_left == node_right){
tree[node] = node_left;
return tree[node];
}
int half = (node_left + node_right) / 2;
int ans_left = initialize(2*node+1, node_left, half);
int ans_right = initialize(2*node+2, half+1, node_right);

if (arr[ans_left] <= arr[ans_right]){
tree[node] = ans_left;
}else{
tree[node] = ans_right;
}
return tree[node];
}

int SegmentTree::query(int node, int node_left, int node_right, int query_left, int query_right) const{
if (node_right < query_left || query_right < node_left) return -1;
if (query_left <= node_left && node_right <= query_right) return tree[node];

int half = (node_left + node_right) / 2;
int ans_left = query(2*node+1, node_left, half, query_left, query_right);
int ans_right = query(2*node+2, half+1, node_right, query_left, query_right);

if (ans_left == -1) return ans_right;
if (ans_right == -1) return ans_left;

return (arr[ans_left] <= arr[ans_right] ? ans_left : ans_right);
}

void SegmentTree::update(int node, int node_left, int node_right, int where, int what){
if (where < node_left || node_right < where) return;
if (node_left == where && where == node_right){
arr[where] = what;
tree[node] = where;
return;
}
int half = (node_left + node_right) / 2;
if (where <= half){
update(2*node+1, node_left, half, where, what);
}else{
update(2*node+2, half+1, node_right, where, what);
}
if (arr[tree[2*node+1]] <= arr[tree[2*node+2]]){
tree[node] = tree[2*node+1];
}else{
tree[node] = tree[2*node+2];
}
}

SegmentTree t;

void build_random_tree(int n = 100){
t.arr.resize(n);
for (int i=0; i old = t.arr;
t.update(where, what);

old[where] = what;
printf("Update [%d] = %d\n", where, what);
assert(t.arr == old);
printf("      SUCCESS\n");
}

void check_random_updates(int times = 100){
while (times--){
int where = random() % t.n, what = random() * (random() % 2 ? -1 : 1);
check_update_correctness(where, what);
//after an update, check some random queries to see if everyting remains fine.
check_random_queries();
}
}

void print_array(const vector &arr){
for (int i=0; i<(int)arr.size(); ++i) printf("%d ", arr[i]);
printf("\n");
}

int main(){
int n = 10;
build_random_tree(n);
check_random_queries(2*n);
check_random_updates();
return 0;
}

```
Problemas relacionados
Nome Comentário
Ainda não há nenhum problema relacionado a esse conteúdo
Sugestão de livro

### Comentários

Postagens neste fórum só são permitidas para membros com conta ativa. Por favor, efetue login or cadastro para postar.