Skip to content

Instantly share code, notes, and snippets.

@shobhit6993
Forked from Se7soz/lazy_segment_tree.cpp
Last active June 6, 2023 21:24
Show Gist options
  • Save shobhit6993/7088061 to your computer and use it in GitHub Desktop.
Save shobhit6993/7088061 to your computer and use it in GitHub Desktop.
C++ implementation of segment tree with lazy propagation.
/**
* 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)
* Actual space required by the tree = 2*2^ceil(log_2(n)) - 1
*/
#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. here 0, N-1 represent the current range.
update_tree(1, 0, N-1, 7, 10, 12); // Incremenet range [7, 10] by 12. here 0, N-1 represent the current range.
update_tree(1, 0, N-1, 10, N-1, 100); // Increment range [10, N-1] by 100. here 0, N-1 represent the current range.
cout << query_tree(1, 0, N-1, 0, N-1) << endl; // Get max element in range [0, N-1]
}
@undershadowww
Copy link

undershadowww commented Nov 23, 2018

i just checked your code and its wrong ? The first update all elements in [0,6] are not fully raised to 5 units

@rohit-100
Copy link

update part seems to be wrong
the update expression should be
tree[node] += lazy[node]*(b-a+1);

@prakhar-srivastav
Copy link

This is max query problem so need for multiplying b-a+1

@Sohaib03
Copy link

Works fine. Tested on various problems. Thanks for sharing.

@NAHDI51
Copy link

NAHDI51 commented Jul 22, 2021

update part seems to be wrong
the update expression should be
tree[node] += lazy[node]*(b-a+1);

This is a segment_tree max.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment