Segment Trees implementation - tips

help
, , ,
1

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?

:frowning:

Bruno

1 Like
2
  1. You can implement a segment tree in a simple way by using a struct for each node. Give indexing to each node of the tree in this way. Let 1 be index of the root of the tree. And 2 * i , 2 * i + 1 are the children of the node with index i. Construct the tree recursively. The only thing one needs to know whether a problem can be solved using segment tree is that if you know the required data about the children, can you construct the present node? So start thinking in that way.
    Here is a pseudo code for tree construction

construct(i, left, right)
{

construct(2 * i, left, mid);

construct(2 * i + 1, mid + 1, right);

logic of how you find the elements of node i;

}

Next when you want to perform query, see where does your range fall starting from root. Lets say that you need the answer of the query [left, right]. Lets start at node. If both left and right are less than the mid value of the range then you need to query only in the left child. So when you go to left child again the problem becomes the same. Same is true when both left and right are greater than mid value. You can descend the tree either to the left child or to the right child. Problem comes when left and right are not on the same side of the mid value. Then again the basic logic comes into play. Query both the sides i.e; from left to mid and from mid + 1 to right. Now you know the answer to two ranges. You need to find the answer to their intersection. Same logic as in construct applies.
Here is a pseudo code

query(int index, int left, int right)

{

if(range exactly matches with the range of the node)

{

return the value in the node

}

if(left <= mid and right <= mid)

return query(2 * index, left, right);

if(left > mid and right > mid)

return query(2 * index + 1, left, right);

//logic

}

Updating is of two types. Single element update and range update. Range update is a bit difficult but updating a single element is easy. This is same as query. Lets say that index pos needs to be updated. Keep on going down in the tree either to the left child or to the right child depending on the position of pos relative to mid value of the nodes. When you get to the leaf node update it and while you come back in recursion, update all the nodes in the path you came.

Update(int index, int pos)

{

if(leaf node)
{

update it

return

}

if(pos <= mid)

update(left child, pos)

else

update(right child, pos)

//basic logic

}

Do basic problems like GSS1, GSS3, FREQUENT.
Then you can implement lazy propagation on your own.

Happy coding :slight_smile: