SEG TREE WITH LAZY

My Experience

Monday, December 24, 2012

Segment Trees and lazy propagation

In this topic i will explain a very interesting data structure that can be used to solve a specific set of problems. I will start by explaining its definition and the proceeding with an example problem to solve with it.

Table of contents:

• What  is segment trees?
• Order of growth of segment trees operations
• Show me your code
• Lazy propagation
• Sample problems to try 
• References

What is segment trees?

Segment Trees is a Tree data structure for storing intervals, or segments, It allows querying which of the stored segments contain a given point. It is, in principle, a static structure; that is, its content cannot be modified once the structure is built. It only uses O(N lg(N)) storage.

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

Building tree: To init the tree segments or intervals values

Update tree: To update value of an interval or segment

Query tree: To retrieve the value of an interval or segment

Example Segment Tree:

• 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 [logN] + 1. Here is how a segment tree for the interval [0, 9] would look like:

 

Order of growth of segment trees operations

• build_tree: O(N lg(N)) 
• update_tree: O(lg(N + k)) 
• query_tree: O(lg(N + k))

K = Number of retrieved intervals or segments

Show me your code

 

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119

/** * 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]; int lazy[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(lazy[node] != 0) { // This node needs to be updated tree[node] += lazy[node]; // Update it   if(a != b) { lazy[node*2] += lazy[node]; // Mark child as lazy lazy[node*2+1] += lazy[node]; // Mark child as lazy }   lazy[node] = 0; // Reset it } if(a > b || a > j || b < i) // Current segment is not within range [i, j] return; if(a >= i && b <= j) { // Segment is fully within range tree[node] += value;   if(a != b) { // Not leaf node lazy[node*2] += value; lazy[node*2+1] += 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(lazy[node] != 0) { // This node needs to be updated tree[node] += lazy[node]; // Update it   if(a != b) { lazy[node*2] += lazy[node]; // Mark child as lazy lazy[node*2+1] += lazy[node]; // Mark child as lazy }   lazy[node] = 0; // Reset it }   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);   memset(lazy, 0, sizeof lazy);   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] }

view rawlazy_segment_tree.cpp hosted with ❤ by GitHub

Lazy Propagation 

Sometimes a segment tree operation wouldn't survive if the problem constraints is too large, here it come lazy propagation along with the segment tree.

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




Note: Read my solution for problem Can you answer these queries I in thi