Hi all,

I have slowly been trying to learn segment trees and while I think I have understood its principle, importance and small examples (RMQ, point and range updates, lazy propagation, etc) I always get stuck in two main things:

a) How to actually go about implementing one;

b) How to decide what the update function should be like for more advanced problems;

I am trying to solve this problem: http://www.spoj.com/problems/BRCKTS/

And, I want to do all of the code mostly from scratch, but, I’ve been looking at some codes and they seem way harder to me than the code for a simple RMQ which shouldn’t possibly (?) be the case, since the under-lying data structure is the same? How to really implement it?

Shall we use Build-Tree, Init-Tree, UpdateOp, QueryOp like, functions? Or should we pack it all in a class, or is it irrelevant?

Here is a code snippet from @mugurelionut for a segTree problem:

```
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
#define VMAX1 333
#define VMAX2 100001
#define MAXPRIMES 10000
#define MAXNODES 3000000
(...)
int vmax[MAXNODES], nvmax[MAXNODES], li[MAXNODES], ls[MAXNODES], lson[MAXNODES], rson[MAXNODES], nnodes;
int root[MAXPRIMES], nmax[MAXPRIMES];
void InitSegTree(int i) {
int node;
root[i] = nnodes + 1;
for (node = nmax[i]; node < 2 * nmax[i]; node++) {
if (node - nmax[i] < vpoz[i].size()) {
vmax[nnodes + node] = vpoz[i][node - nmax[i]].first;
li[nnodes + node] = ls[nnodes + node] = vpoz[i][node - nmax[i]].second;
} else {
vmax[nnodes + node] = -2;
li[nnodes + node] = ls[nnodes + node] = N + 1;
}
nvmax[nnodes + node] = 1;
lson[nnodes + node] = rson[nnodes + node] = 0;
}
for (node = nmax[i] - 1; node >= 1; node--) {
lson[nnodes + node] = nnodes + (node << 1);
rson[nnodes + node] = lson[nnodes + node] + 1;
li[nnodes + node] = li[lson[nnodes + node]];
ls[nnodes + node] = ls[rson[nnodes + node]];
if (vmax[lson[nnodes + node]] > vmax[rson[nnodes + node]]) {
vmax[nnodes + node] = vmax[lson[nnodes + node]];
nvmax[nnodes + node] = nvmax[lson[nnodes + node]];
} else if (vmax[lson[nnodes + node]] < vmax[rson[nnodes + node]]) {
vmax[nnodes + node] = vmax[rson[nnodes + node]];
nvmax[nnodes + node] = nvmax[rson[nnodes + node]];
} else {
vmax[nnodes + node] = vmax[rson[nnodes + node]];
nvmax[nnodes + node] = nvmax[lson[nnodes + node]] + nvmax[rson[nnodes + node]];
}
}
nnodes += 2 * nmax[i];
}
void BuildSegmentTrees() {
int i, j;
nnodes = 0;
for (i = 0; i < np; i++) {
if (vpoz[i].size() == 0) {
nmax[i] = 0;
continue;
}
nmax[i] = 2;
while (nmax[i] < vpoz[i].size()) nmax[i] <<= 1;
InitSegTree(i);
//fprintf(stderr, "%d %d\n", i, nmax[i]);
}
}
int QA, QB, QVMAX, QNVMAX;
void QuerySegTree(int node) {
if (QA <= li[node] && ls[node] <= QB) {
if (vmax[node] > QVMAX) {
QVMAX = vmax[node];
QNVMAX = nvmax[node];
} else if (vmax[node] == QVMAX) {
QNVMAX += nvmax[node];
}
return;
}
if (lson[node] == 0 || rson[node] == 0)
return;
if (QA <= ls[lson[node]])
QuerySegTree(lson[node]);
if (QB >= li[rson[node]])
QuerySegTree(rson[node]);
}
void ProcessQueries() {
int G, x, y, i, ansvmax, ansnvmax;
while (M--) {
scanf("%d %d %d", &G, &x, &y);
Decompose(G);
ansvmax = ansnvmax = -1;
for (i = 0; i < nd; i++) {
if (nmax[d[i]] == 0) continue;
QA = x; QB = y; QVMAX = -2; QNVMAX = 0;
//fprintf(stderr, "-- query %d: %d %d | %d %d:%d %d:%d\n", d[i], root[d[i]], nmax[d[i]], vmax[root[d[i]]], lson[root[d[i]]], vmax[lson[root[d[i]]]], rson[root[d[i]]], vmax[rson[root[d[i]]]]);
QuerySegTree(root[d[i]]);
if (QVMAX > ansvmax) {
ansvmax = QVMAX;
ansnvmax = QNVMAX;
}
}
printf("%d %d\n", ansvmax, ansnvmax);
}
}
```

If I could use that BRCKTS problem from SPOJ to write something similar for myself, it would be really great…

Any help from where to start?

All I know is that we have a point update “masked” as the replacement operation…The check operation is what? A range query? To check for the entire expression?

Bruno