FANDOM


Segment Trees is a Tree Data Structure for storing intervals or segments. It allows querying which of the stored segments have a specific property. It is, in principle, a static structure; that is, its content cannot be modified once the structure is built. It uses O(4*N) storage, where N is the size of the segment.

Queries Edit

A segment tree has only three operations: build_tree, update_tree, query_tree.

Building tree: To init the tree segments or interval values, O(N log(N)) time

Update tree: To update value of an interval or segment, O(log(N+k)) time

Query tree: To retrieve the value of an interval or segment, O(log(N+k)) time

K = Number of retrieved intervals or segments

Example Segment Tree: Edit

  • Seqment trees
    The first node will hold the information for the interval [i, j]
  • if i<j, the left and right son will hold the information for the intervals [i, (i+j)/2] and [(i+j)/2 + 1, j]

Notice that the height of a segment tree for an interval with N elements is [log N] + 1. Here is how a segment tree for the interval [0,9] would look like:

Code Edit

/**
 * In this code we have a very large array called arr, and very large set of operations
 * Operation #1: Increment the elements within range [i, j] with value val
 * Operation #2: Get max element within range [i, j]
 * Build tree: build_tree(1, 0, N-1)
 * Update tree: update_tree(1, 0, N-1, i, j, value)
 * Query tree: query_tree(1, 0, N-1, i, j)
 */
 
 #include<iostream>
#include<algorithm>
using namespace std;

#include<string.h>
#include<math.h> 

#define N 20
 #define MAX (1+(1<<6)) // Why? :D
 #define inf 0x7fffffff

int arr[N];
int tree[MAX];

/**
 * Build and init tree
 */
 void build_tree(int node, int a, int b) {
     if(a > b) return; // Out of range
  	
   	if(a == b) { // Leaf node
    		tree[node] = arr[a]; // Init value
		return;
	}
	
	build_tree(node*2, a, (a+b)/2); // Init left child
	build_tree(node*2+1, 1+(a+b)/2, b); // Init right child
	
	tree[node] = max(tree[node*2], tree[node*2+1]); // Init root value
}

/**
 * Increment elements within range [i, j] with value value
 */
 void update_tree(int node, int a, int b, int i, int j, int value) {
     
 	if(a > b || a > j || b < i) // Current segment is not within range [i, j]
 		return;
     
   	if(a == b) { // Leaf node
    		tree[node] += value;
    		return;
 	}
 
 	update_tree(node*2, a, (a+b)/2, i, j, value); // Updating left child
 	update_tree(1+node*2, 1+(a+b)/2, b, i, j, value); // Updating right child
 
 	tree[node] = max(tree[node*2], tree[node*2+1]); // Updating root with max value
 }
 
 /**
  * Query tree to get max element value within range [i, j]
 */
 int query_tree(int node, int a, int b, int i, int j) {
 	
 	if(a > b || a > j || b < i) return -inf; // Out of range
 
 	if(a >= i && b <= j) // Current segment is totally within range [i, j]
 		return tree[node];
 
 	int q1 = query_tree(node*2, a, (a+b)/2, i, j); // Query left child
 	int q2 = query_tree(1+node*2, 1+(a+b)/2, b, i, j); // Query right child
 
 	int res = max(q1, q2); // Return final result
 	
 	return res;
 }
 
 int main() {
 	for(int i = 0; i < N; i++) arr[i] = 1;
 
 	build_tree(1, 0, N-1);
 
 	update_tree(1, 0, N-1, 0, 6, 5); // Increment range [0, 6] by 5
 	update_tree(1, 0, N-1, 7, 10, 12); // Incremenet range [7, 10] by 12
 	update_tree(1, 0, N-1, 10, N-1, 100); // Increment range [10, N-1] by 100
 
 	cout << query_tree(1, 0, N-1, 0, N-1) << endl; // Get max element in range [0, N-1]
 }

Lazy Propagation Edit

The above code works perfectly for small / point updates, but for range updates for longer ranges, we need lazy propagation along with segment tree.

In the current version, when we update a range, we branch its children even if the segment is covered within range. In the lazy version, we only mark its child that needs to be updated and update it when needed

/**
 * In this code we have a very large array called arr, and very large set of operations
 * Operation #1: Increment the elements within range [i, j] with value val
 * Operation #2: Get max element within range [i, j]
 * Build tree: build_tree(1, 0, N-1)
 * Update tree: update_tree(1, 0, N-1, i, j, value)
 * Query tree: query_tree(1, 0, N-1, i, j)
 */
 
 #include<iostream>
#include<algorithm>
using namespace std;

#include<string.h>
#include<math.h> 

#define N 20
 #define MAX (1+(1<<6)) // Why? :D
 #define inf 0x7fffffff

int arr[N];
int tree[MAX];

/**
 * Build and init tree
 */
 void build_tree(int node, int a, int b) {
     if(a > b) return; // Out of range
  	
   	if(a == b) { // Leaf node
    		tree[node] = arr[a]; // Init value
		return;
	}
	
	build_tree(node*2, a, (a+b)/2); // Init left child
	build_tree(node*2+1, 1+(a+b)/2, b); // Init right child
	
	tree[node] = max(tree[node*2], tree[node*2+1]); // Init root value
}

/**
 * Increment elements within range [i, j] with value value
 */
 void update_tree(int node, int a, int b, int i, int j, int value) {
     
 	if(a > b || a > j || b < i) // Current segment is not within range [i, j]
 		return;
     
   	if(a == b) { // Leaf node
    		tree[node] += value;
    		return;
 	}
 
 	update_tree(node*2, a, (a+b)/2, i, j, value); // Updating left child
 	update_tree(1+node*2, 1+(a+b)/2, b, i, j, value); // Updating right child
 
 	tree[node] = max(tree[node*2], tree[node*2+1]); // Updating root with max value
 }
 
 /**
  * Query tree to get max element value within range [i, j]
 */
 int query_tree(int node, int a, int b, int i, int j) {
 	
 	if(a > b || a > j || b < i) return -inf; // Out of range
 
 	if(a >= i && b <= j) // Current segment is totally within range [i, j]
 		return tree[node];
 
 	int q1 = query_tree(node*2, a, (a+b)/2, i, j); // Query left child
 	int q2 = query_tree(1+node*2, 1+(a+b)/2, b, i, j); // Query right child
 
 	int res = max(q1, q2); // Return final result
 	
 	return res;
 }
 
 int main() {
 	for(int i = 0; i < N; i++) arr[i] = 1;
 
 	build_tree(1, 0, N-1);
 
 	update_tree(1, 0, N-1, 0, 6, 5); // Increment range [0, 6] by 5
 	update_tree(1, 0, N-1, 7, 10, 12); // Incremenet range [7, 10] by 12
 	update_tree(1, 0, N-1, 10, N-1, 100); // Increment range [10, N-1] by 100
 
 	cout << query_tree(1, 0, N-1, 0, N-1) << endl; // Get max element in range [0, N-1]
 }

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.