Building Segment Trees Iteratively: A Step-by-Step Guide
This blog aims to explain a simple iterative segment tree that is easy to memorize due to its step-by-step approach while remaining efficient. This segment tree is designed for competitive programming contests that do not allow templates but still require this technique to be implemented quickly.
Introduction
The segment tree is a data structure that enables range queries with updates. In this blog, I will demonstrate how to construct an iterative segment tree with this approach to solve the following operations:
- Query the minimum value in a range.
- Add a given value to each element in a range.
Step 1: Preparations
To begin, we need to adjust the size of the given array. For instance, if the array is named $$$A$$$ and has a size $$$N$$$, we must find the smallest power of $$$2$$$ greater than or equal to $$$N$$$. This adjustment is possible because the additional values we append to $$$A$$$ will never be accessed. To achieve this, we first implement the function $$$\text{getPower(N)}$$$.
// Function to find the smallest power of 2 greater than or equal to n
int getPower(int n) {
int l = 0, r = 26; // Define the binary search range for powers of 2
while (l < r) {
int mid = (l + r) / 2; // Calculate the midpoint of the range
if ((1 << mid) >= n) { // Check if 2^mid is greater than or equal to n
r = mid; // Narrow the search range to the left
} else {
l = mid + 1; // Narrow the search range to the right
}
}
return l; // Return the smallest power of 2
}
At this point, $$$N$$$ is now a power of $$$2$$$, so it is essential to keep this detail in mind moving forward.
Step 2: Creating the Segment Tree
As we know, a Segment Tree is a binary tree that, when the original array (of size $$$N$$$) has a size that is a power of $$$2$$$, uses $$$2N$$$ nodes. Since $$$N$$$ is a power of $$$2$$$, the indices corresponding to $$$A$$$ in the Segment Tree will be $$$i+n-1$$$. The construction takes advantage of the fact that if we have a node with index $$$x$$$, then its parent is $$$\frac{x}{2}$$$. To build the Segment Tree, we first assign the values of the array to the leaves, and then for each node, we combine the results of its children to form each node. The children of each node are $$$2*x$$$ and $$$2x+1$$$.
vector<int> st(2 * n + 1), lz(2 * n + 1), A(n + 1);
// Function to build the segment tree
void build() {
// Assign values from the array to the leaves of the segment tree
for (int i = 1; i <= n; i++) {
A[i] = st[i + n - 1]; // Map array elements to the corresponding leaf nodes
}
// Combine child nodes to form parent nodes
for (int i = n - 1; i >= 1; i--) {
st[i] = min(st[2 * i], st[2 * i + 1]); // Compute the minimum of the left and right children
}
}
With this, the segment tree is ready to start performing queries and modifications.
Step 3: Creating the Query Function
To solve the problems, we need to view everything from the leaves to the root. Suppose we want a query in the interval $$$[a,b]$$$. Since we know that $$$N$$$ is a power of $$$2$$$, the node for $$$a$$$ will be $$$a+N - 1$$$ and similarly for $$$b$$$. However, this is not enough to solve the problem, as we need to filter which nodes are the main ones for our interval and which are not. To do this, we define $$$L$$$ and $$$R$$$ as the left and right limits, respectively. If the left limit is at a left node, then that node is not a definitive node in the interval because, as $$$R$$$ is the right limit, the node $$$L+1$$$ is also part of the interval, or if $$$L=R$$$, then either $$$L$$$ is on the right and necessary, or $$$R$$$ is on the left and necessary. The same applies to $$$R$$$, but in reverse.
// Function to query the minimum value in a range [a, b]
int query(int a, int b) {
int l = a + n - 1, r = b + n - 1; // Convert range to segment tree indices
bool reg = false; // Flag to check if the result is initialized
int ans = 0; // Variable to store the result
while (l <= r) {
if (l % 2 == 1) { // If l is a right child
propagateUpToX(l); // Propagate updates to the current node
ans = reg ? min(ans, st[l]) : st[l]; // Update the result with the minimum value
reg = true; // Mark the result as initialized
l++; // Move to the next node
}
if (r % 2 == 0) { // If r is a left child
propagateUpToX(r); // Propagate updates to the current node
ans = reg ? min(ans, st[r]) : st[r]; // Update the result with the minimum value
reg = true; // Mark the result as initialized
r--; // Move to the previous node
}
l /= 2; // Move to the parent node
r /= 2; // Move to the parent node
}
return ans; // Return the minimum value in the range
}
At this point, we have a function that solves the minimum query, so now let's see how to add range updates with lazy propagation.
Step 4: Adding Lazy Propagation
Now that we have finished the first point, we need to start with the next point. To address this problem, we will use the lazy propagation technique, which involves placing an update tag and updating only when necessary. Usually, this technique is implemented from the root node to the leaves (note that this is the reverse of our iterative segment tree), but we can take advantage of something to make the same traversal, and that is the binary representation of numbers, from the highest power to the lowest. If that power is present, we move to the right; otherwise, we move to the left. As we progress through the nodes to be updated, the update tags are propagated. The main update function goes down to the leaves, captures the main nodes, and calls the rest of the functions we have defined.
// Function to propagate lazy updates to a node
void propagate(int x) {
st[x] += lz[x]; // Apply the lazy value to the current node
if (x < n) { // If the node is not a leaf
lz[2 * x] += lz[x]; // Propagate the lazy value to the left child
lz[2 * x + 1] += lz[x]; // Propagate the lazy value to the right child
}
lz[x] = 0; // Clear the lazy value for the current node
}
// Function to propagate updates from the root to a specific node x
void propagateUpToX(int x) {
int cur = x, h = 0; // Start from the target node and calculate its height
while (cur > 0) {
h++; // Increment the height
cur /= 2; // Move to the parent node
}
cur = 1; // Start from the root
for (int i = h - 2; i >= 0; i--) {
propagate(cur); // Propagate updates to the current node
cur = (x & (1 << i)) ? 2 * cur + 1 : 2 * cur; // Move to the left or right child based on the bit
}
propagate(cur); // Propagate updates to the target node
}
// Function to update the segment tree up to a specific node x
void updateUpToX(int x) {
int cur = x; // Start from the target node
propagate(cur); // Propagate updates to the current node
cur /= 2; // Move to the parent node
while (cur > 0) {
propagate(cur); // Propagate updates to the current node
propagate(2 * cur); // Propagate updates to the left child
propagate(2 * cur + 1); // Propagate updates to the right child
st[cur] = min(st[2 * cur], st[2 * cur + 1]); // Update the current node with the minimum value of its children
cur /= 2; // Move to the parent node
}
}
// Function to update a range [a, b] with a value v
void update(int a, int b, int v) {
int l = a + n - 1, r = b + n - 1; // Convert range to segment tree indices
while (l <= r) {
if (l % 2 == 1) { // If l is a right child
propagateUpToX(l); // Propagate updates to the current node
lz[l] += v; // Add the value to the lazy array
updateUpToX(l); // Update the segment tree up to the current node
l++; // Move to the next node
}
if (r % 2 == 0) { // If r is a left child
propagateUpToX(r); // Propagate updates to the current node
lz[r] += v; // Add the value to the lazy array
updateUpToX(r); // Update the segment tree up to the current node
r--; // Move to the previous node
}
l /= 2; // Move to the parent node
r /= 2; // Move to the parent node
}
}
With this, we have range updates, but one thing is missing. The query section also requires updating the nodes up to the nodes we need, and for that, we just need to add a few lines to the code.
// Function to query the minimum value in a range [a, b]
int query(int a, int b) {
int l = a + n - 1, r = b + n - 1; // Convert range to segment tree indices
bool reg = false; // Flag to check if the result is initialized
int ans = 0; // Variable to store the result
while (l <= r) {
if (l % 2 == 1) { // If l is a right child
propagateUpToX(l); // Propagate updates to the current node
ans = reg ? min(ans, st[l]) : st[l]; // Update the result with the minimum value
reg = true; // Mark the result as initialized
l++; // Move to the next node
}
if (r % 2 == 0) { // If r is a left child
propagateUpToX(r); // Propagate updates to the current node
ans = reg ? min(ans, st[r]) : st[r]; // Update the result with the minimum value
reg = true; // Mark the result as initialized
r--; // Move to the previous node
}
l /= 2; // Move to the parent node
r /= 2; // Move to the parent node
}
return ans; // Return the minimum value in the range
}
All the code together would be:
// Organized and cleaned-up code for better readability
// Global variables
vector<int> st(2 * n + 1), lz(2 * n + 1), A(n + 1);
// Function to find the smallest power of 2 greater than or equal to n
int getPower(int n) {
int l = 0, r = 26; // Define the binary search range for powers of 2
while (l < r) {
int mid = (l + r) / 2; // Calculate the midpoint of the range
if ((1 << mid) >= n) { // Check if 2^mid is greater than or equal to n
r = mid; // Narrow the search range to the left
} else {
l = mid + 1; // Narrow the search range to the right
}
}
return l; // Return the smallest power of 2
}
// Function to build the segment tree
void build() {
// Assign values from the array to the leaves of the segment tree
for (int i = 1; i <= n; i++) {
A[i] = st[i + n - 1]; // Map array elements to the corresponding leaf nodes
}
// Combine child nodes to form parent nodes
for (int i = n - 1; i >= 1; i--) {
st[i] = min(st[2 * i], st[2 * i + 1]); // Compute the minimum of the left and right children
}
}
// Function to propagate lazy updates to a node
void propagate(int x) {
st[x] += lz[x]; // Apply the lazy value to the current node
if (x < n) { // If the node is not a leaf
lz[2 * x] += lz[x]; // Propagate the lazy value to the left child
lz[2 * x + 1] += lz[x]; // Propagate the lazy value to the right child
}
lz[x] = 0; // Clear the lazy value for the current node
}
// Function to propagate updates from the root to a specific node x
void propagateUpToX(int x) {
int cur = x, h = 0; // Start from the target node and calculate its height
while (cur > 0) {
h++; // Increment the height
cur /= 2; // Move to the parent node
}
cur = 1; // Start from the root
for (int i = h - 2; i >= 0; i--) {
propagate(cur); // Propagate updates to the current node
cur = (x & (1 << i)) ? 2 * cur + 1 : 2 * cur; // Move to the left or right child based on the bit
}
propagate(cur); // Propagate updates to the target node
}
// Function to update the segment tree up to a specific node x
void updateUpToX(int x) {
int cur = x; // Start from the target node
propagate(cur); // Propagate updates to the current node
cur /= 2; // Move to the parent node
while (cur > 0) {
propagate(cur); // Propagate updates to the current node
propagate(2 * cur); // Propagate updates to the left child
propagate(2 * cur + 1); // Propagate updates to the right child
st[cur] = min(st[2 * cur], st[2 * cur + 1]); // Update the current node with the minimum value of its children
cur /= 2; // Move to the parent node
}
}
// Function to update a range [a, b] with a value v
void update(int a, int b, int v) {
int l = a + n - 1, r = b + n - 1; // Convert range to segment tree indices
while (l <= r) {
if (l % 2 == 1) { // If l is a right child
propagateUpToX(l); // Propagate updates to the current node
lz[l] += v; // Add the value to the lazy array
updateUpToX(l); // Update the segment tree up to the current node
l++; // Move to the next node
}
if (r % 2 == 0) { // If r is a left child
propagateUpToX(r); // Propagate updates to the current node
lz[r] += v; // Add the value to the lazy array
updateUpToX(r); // Update the segment tree up to the current node
r--; // Move to the previous node
}
l /= 2; // Move to the parent node
r /= 2; // Move to the parent node
}
}
// Function to query the minimum value in a range [a, b]
int query(int a, int b) {
int l = a + n - 1, r = b + n - 1; // Convert range to segment tree indices
bool reg = false; // Flag to check if the result is initialized
int ans = 0; // Variable to store the result
while (l <= r) {
if (l % 2 == 1) { // If l is a right child
propagateUpToX(l); // Propagate updates to the current node
ans = reg ? min(ans, st[l]) : st[l]; // Update the result with the minimum value
reg = true; // Mark the result as initialized
l++; // Move to the next node
}
if (r % 2 == 0) { // If r is a left child
propagateUpToX(r); // Propagate updates to the current node
ans = reg ? min(ans, st[r]) : st[r]; // Update the result with the minimum value
reg = true; // Mark the result as initialized
r--; // Move to the previous node
}
l /= 2; // Move to the parent node
r /= 2; // Move to the parent node
}
return ans; // Return the minimum value in the range
}
Conclusion
In this blog, we explored the implementation of an iterative segment tree, a powerful data structure for solving range queries and updates efficiently. We started by understanding the basics of segment trees, followed by step-by-step explanations of building the tree, querying ranges, and implementing lazy propagation for range updates. The iterative approach presented here is designed to be simple, efficient, and easy to implement in competitive programming scenarios.
Thank you for taking the time to read this blog. I hope it has been helpful in deepening your understanding of segment trees. If you have any questions, feedback, or suggestions, feel free to share them. Happy coding!!!
