Segment Tree

Segment trees (for beginners)
--------------------------------------

Lets start with a simple problem.

Given an array of numbers. There are 2 types of operations to do.
1. update any element in the array
2. find the maximum/minimum in the given range (i,j)

Simple solution.
-- updating is no problem. a[i]=x; :D
-- finding 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 in O(log n) where n is the size of the array.

That's when segment tree comes handy.


A Segment Tree is a binary 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 in Segment Trees as 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 8.

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 8.

Assume such tree exists. Lets walk through how we process the following queries.


1. Find maximum in range (1,8)

Return the answer stored in the root of the tree.


2. Find maximum in range (3,6)


check root(1-8) ---(our range is a subset of this range) so branch in.
check (1-4) hmm..contains partially
check (1-2) out of range...dont check its children.
check (3-4) hmm..completely inside the range...take the value..dont go to children(since it lies completely inside the range (3,6) ).
check (5-8) hmm...contains our answer partially
check (5-6) completely inside our range. so take its info. dont branch in.
check (7-8) completely outside our range. dont branch in.


Now finally compare all the values we took in the process.
Remember we took the values of range(3-4) and (5-6)
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.

***********Happy Coding*******************


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 2*n and 2*n + 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] );

}


//query function is homework.

int query(int n, int b, int e, int i, int j) //return the maximum in the range (i,j)
{
...
...
}

/******************************************************************************/
/******************************************************************************/
/******************************************************************************/

The problem of finding maximum in the range requires a little more effort.

Reason:

-> lazy propagation updates 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;
}
}




**************************************************************************