Segment trees (for beginners)

Lets start with a simple problem.Given an array of numbers. There are 2 types of operations to do.update any element in the arrayfind the maximum/minimum in the given range (i,j)Simple solution.updating is no problem. a[i]=x; :Dfinding maximum/minimum can be done in one for loop of (j-i+1) iterations.Can we do any better?The answer is yes.In fact we can do both the operation inO(log n)where n is the size of the array.That’s when segment tree comes handy.ASegment Treeis abinary tree.
For the sake of convinience, lets take an array of size N = 2^n.Suppose we have some work to do. If one person does it all, a lot of
effort/time is needed. So to reduce the time as well as effort we can divide the
responsibilities among many people.We can divide the responsibilities inSegment Treesas well.Lets distribute the responsibilities to different nodes as follows.each node carries the maximum and/or minimum value of all its
childrens.For example:
Suppose we have an array of size 5.Let us construct a complete binary tree (segment tree) as below.In a segment tree the list of leaf nodes represents the actual array where the main data resides. Here there are 8 leaf nodes which correspond to the elements of array we wish to update or find max/min in the range.Each node stores the required information (here maximum/minimum) assigned to them.
for eg: The root node stores maximum/minimum of all the nodes from node 1 to node 5.Assume such tree exists. Lets walk through how we process the following queries.1. Find maximum in range (1,5)Return the answer stored in the root of the tree.2. Find maximum in range (2,5)check root(1-5) —(our range is a subset of this range) so branch in.
check (1-2) hmm..contains partially check (1) out of range…dont
check its children. check (2) hmm..completely inside the range…take
the value..dont go to children(since it lies completely inside the
range (2,5) ). check (3-5) completely inside our range. so take its
info. dont branch in.Now finally compare all the values we took in the process.
Remember we took the values of range(2) and (3-5)
Just compare them and we have the maximum.Here we visited none of the leaf nodes. We visited some internal nodes only.
In practice if the segment tree is very large then we skip too many nodes.
So effectively the number of nodes examined will be of order of O(height) the tree.
which is log N.Let me give you how to build the tree for finding maximum in a range.
A binary tree can be represented by an array. For convenience I have named the root as 1. The 2 children of a node n are 2n and 2n + 1.If you have an array ‘arr’ of size 1000, then call build function as below.
build (1, 0, 999);int tree[3*MAX]; //a segment tree is nearly twice as large as the array.
int arr[MAX];

void build(int n, int b, int e)
{
if (b>e) return;
else if (b==e)
{
tree[n] = arr[b];
return;
}

build ( n*2 , b , (b+e)/2 ); //go to children…child nodes of node n are 2n and 2n+1.

build (n*2+1, (b+e)/2 + 1 , e );

//now both child nodes 2n and 2n+1 are built (ie they have done their responsibility of storing the correct information)
tree[n] = max( tree[n*2] , tree[n*2 + 1] );

}

/*
* update in the tree at index idx with value val.
* remember here n is the node number of the tree and not index of array…value of root node 1 and its children are 2 and 3
* idx is the mapping of the leaf nodes to array. when b==e we reached leaf node
*/
void update(int n, int b, int e, int idx, int val)
{
if (b>e || b>idx || e<idx ) return;
if (b==e) //at leaf node
{
tree[n] = val;
return;
}

update( n*2 , b , (b+e)/2 , idx, val );
update( n*2 + 1 , (b+e)/2 + 1 , e , idx, val );

//now some change might have been made in either of the child nodes.

tree[n] = max( tree[n*2] , tree[n*2 + 1] );

}

//similarly for query functions…The problem of finding maximum in the range requires a little more effort.
Reason:
->lazy propagationupdates only at top level nodes.
-> each node can either store increments done to the range or only the maximum.
having only one of these is not sufficient.Thus we need to store both the information. store 2 variables. one is
maximum of the child nodes and another is total increment done to the
node.the actual maximum number at each node is
maximum number stored in a node + total increments to the node and all its parents.Below is full source code of the program.#include < cstdio >
#include < iostream >
using namespace std;

#define INF 1e9

struct Node {
int offt;
int cmax;
} tree[5000];

void update(int n, int b, int e, int i, int j, int val)
{
if (b>e || i>j || b>j || e

if (b>=i && e<=j)
{
tree[n].offt += val;
tree[n].cmax += val;
return;
}

update(n*2 , b , (b+e)/2 , i , j , val);
update(n*2+1 , (b+e)/2 + 1 , e , i , j , val);

tree[n].cmax = max ( tree[n*2].cmax , tree[n*2+1].cmax ) + tree[n].offt;
}

int query(int n, int b, int e, int i, int j, int offt)
{
if (b>e || i>j || b>j || e

if (b>=i && e<=j)
return tree[n].cmax + offt; //the increment of current node is already added to cmax here (see update function)

offt += tree[n].offt;
return max ( query(n*2 , b , (b+e)/2 , i , j, offt) ,
query(n*2+1 , (b+e)/2 + 1 , e , i , j, offt) );
}

int main()
{
int tc,x,a,b,v;
cin >> tc;
while(tc–)
{
cin >> x >> a >> b;
if ( x == 0 )
{
cin >> v;
update(1,0,999,a,b,v);
}
else
cout << query(1,0,999,a,b,0) << endl;
}
}

News Reporter

Leave a Reply

Your email address will not be published. Required fields are marked *