Table of contents
Welcome to Day 33 of my 100 Days of DSA challenge! Today’s focus was on mastering the fundamentals of segment trees, a versatile data structure designed for efficient range queries and updates. From implementing basic range sum queries to solving problems like range minimum and XOR queries, I delved into understanding and applying this powerful tool. Check out my GitHub repository for all my solutions and progress.
Check out my GitHub repository for all the solutions and progress updates at: 100 Days of DSA
Let’s keep learning! 🚀
1. Segment Tree to Find the Sum of a Range in an Array
This program uses a segment tree to efficiently compute the sum of elements in a given range and to update elements in the array. The build_tree function constructs the segment tree, range_sum computes the sum for a given range, and update_tree updates a specific index in the array. The get_range_sum and update methods expose these functionalities for user interaction.
Code:
#include <iostream>
using namespace std;
#define MAX 1000
class SegmentTree {
private:
int segment_tree[4 * MAX];
int array[MAX];
int size;
// Helper function to build the segment tree
void build_tree(int node, int start, int end) {
if (start == end) {
segment_tree[node] = array[start];
} else {
int mid = (start + end) / 2;
int left_child = 2 * node + 1;
int right_child = 2 * node + 2;
build_tree(left_child, start, mid);
build_tree(right_child, mid + 1, end);
segment_tree[node] = segment_tree[left_child] + segment_tree[right_child];
}
}
// Helper function for range sum query
int range_sum(int node, int start, int end, int left, int right) {
if (right < start || left > end) {
return 0; // Outside range
}
if (left <= start && end <= right) {
return segment_tree[node]; // Fully inside range
}
int mid = (start + end) / 2;
int left_child = 2 * node + 1;
int right_child = 2 * node + 2;
int sum_left = range_sum(left_child, start, mid, left, right);
int sum_right = range_sum(right_child, mid + 1, end, left, right);
return sum_left + sum_right;
}
// Helper function to update the segment tree
void update_tree(int node, int start, int end, int idx, int value) {
if (start == end) {
array[idx] = value;
segment_tree[node] = value;
} else {
int mid = (start + end) / 2;
int left_child = 2 * node + 1;
int right_child = 2 * node + 2;
if (idx <= mid) {
update_tree(left_child, start, mid, idx, value);
} else {
update_tree(right_child, mid + 1, end, idx, value);
}
segment_tree[node] = segment_tree[left_child] + segment_tree[right_child];
}
}
public:
// Initialize the segment tree
void initialize(int arr[], int n) {
size = n;
for (int i = 0; i < n; i++) {
array[i] = arr[i];
}
build_tree(0, 0, size - 1);
}
// Perform a range sum query
int get_range_sum(int left, int right) {
return range_sum(0, 0, size - 1, left, right);
}
// Update a specific index in the array
void update(int idx, int value) {
update_tree(0, 0, size - 1, idx, value);
}
};
int main() {
int arr[] = {1, 3, 5, 7, 9, 11};
int n = sizeof(arr) / sizeof(arr[0]);
SegmentTree segment_tree;
segment_tree.initialize(arr, n);
cout << "Sum of range [1, 3]: " << segment_tree.get_range_sum(1, 3) << endl;
segment_tree.update(1, 10);
cout << "Sum of range [1, 3]: " << segment_tree.get_range_sum(1, 3) << endl;
return 0;
}
Output:
2. Modified Segment Tree that Supports Point Updates and Range Queries
This program implements a segment tree to support point updates and range queries. It uses a fixed-size array for the segment tree. The tree is constructed by recursively dividing the array into halves and storing the sum of elements in each segment. Updates are handled by modifying the necessary segments, and range queries return the sum of elements within the specified range by traversing relevant segments of the tree.
Code:
#include <iostream>
#include <cstring>
using namespace std;
#define MAX 1000
class SegmentTree {
private:
int tree[MAX * 4]; // Segment tree array
int arr[MAX]; // Input array
int size; // Size of the input array
// Build the segment tree
void build_tree(int node, int start, int end) {
if (start == end) {
tree[node] = arr[start]; // Leaf node
} else {
int mid = (start + end) / 2;
int left_child = 2 * node + 1;
int right_child = 2 * node + 2;
build_tree(left_child, start, mid);
build_tree(right_child, mid + 1, end);
tree[node] = tree[left_child] + tree[right_child]; // Combine results
}
}
// Perform a point update on the segment tree
void update_tree(int node, int start, int end, int idx, int value) {
if (start == end) {
arr[idx] = value; // Update the array
tree[node] = value; // Update the tree
} else {
int mid = (start + end) / 2;
int left_child = 2 * node + 1;
int right_child = 2 * node + 2;
if (idx <= mid) {
update_tree(left_child, start, mid, idx, value);
} else {
update_tree(right_child, mid + 1, end, idx, value);
}
tree[node] = tree[left_child] + tree[right_child]; // Recalculate parent
}
}
// Perform a range query
int query_tree(int node, int start, int end, int l, int r) {
if (r < start || l > end) {
return 0; // Out of range
}
if (l <= start && r >= end) {
return tree[node]; // Completely in range
}
int mid = (start + end) / 2;
int left_child = 2 * node + 1;
int right_child = 2 * node + 2;
int left_sum = query_tree(left_child, start, mid, l, r);
int right_sum = query_tree(right_child, mid + 1, end, l, r);
return left_sum + right_sum; // Combine results
}
public:
// Initialize the segment tree
void initialize(int input_arr[], int n) {
size = n;
for (int i = 0; i < n; i++) {
arr[i] = input_arr[i];
}
build_tree(0, 0, size - 1);
}
// Update a value at a specific index
void update(int idx, int value) {
update_tree(0, 0, size - 1, idx, value);
}
// Query the sum of a range
int query(int l, int r) {
return query_tree(0, 0, size - 1, l, r);
}
};
int main() {
int n = 6;
int input_arr[] = {1, 3, 5, 7, 9, 11};
SegmentTree seg_tree;
seg_tree.initialize(input_arr, n);
cout << "Initial range sum (1 to 3): " << seg_tree.query(1, 3) << endl;
seg_tree.update(1, 10);
cout << "After update, range sum (1 to 3): " << seg_tree.query(1, 3) << endl;
seg_tree.update(3, 6);
cout << "After another update, range sum (0 to 5): " << seg_tree.query(0, 5) << endl;
return 0;
}
Output:
3. Range Minimum Query (RMQ) Problem
This program solves the Range Minimum Query (RMQ) problem using a segment tree. It uses a segment_tree array to store the tree. The build_tree function recursively constructs the tree, and query_tree handles the range minimum queries by dividing the range and finding the minimum. The initialize function sets up the segment tree, and range_minimum_query processes user queries by calling query_tree.
Code:
#include <iostream>
#include <climits>
using namespace std;
#define MAX 1000
class Segment_Tree {
private:
int segment_tree[4 * MAX]; // Array to store the segment tree
int array[MAX]; // Input array
int size; // Size of the input array
// Build the segment tree
void build_tree(int node, int start, int end) {
if (start == end) {
segment_tree[node] = array[start]; // Leaf node
} else {
int mid = (start + end) / 2;
build_tree(2 * node + 1, start, mid); // Build left child
build_tree(2 * node + 2, mid + 1, end); // Build right child
segment_tree[node] = min(segment_tree[2 * node + 1], segment_tree[2 * node + 2]); // Store minimum
}
}
// Query the segment tree for minimum in range [left, right]
int query_tree(int node, int start, int end, int left, int right) {
if (start > right || end < left) {
return INT_MAX; // Out of range
}
if (start >= left && end <= right) {
return segment_tree[node]; // Fully within range
}
int mid = (start + end) / 2;
int left_min = query_tree(2 * node + 1, start, mid, left, right);
int right_min = query_tree(2 * node + 2, mid + 1, end, left, right);
return min(left_min, right_min); // Return minimum of both ranges
}
public:
// Initialize the segment tree
void initialize(int arr[], int n) {
size = n;
for (int i = 0; i < n; i++) {
array[i] = arr[i];
}
build_tree(0, 0, size - 1); // Build the segment tree
}
// Query for minimum in range [left, right]
int range_minimum_query(int left, int right) {
return query_tree(0, 0, size - 1, left, right);
}
};
int main() {
int array[MAX], n, queries, left, right;
cout << "Enter the number of elements: ";
cin >> n;
cout << "Enter the elements: ";
for (int i = 0; i < n; i++) {
cin >> array[i];
}
Segment_Tree seg_tree;
seg_tree.initialize(array, n);
cout << "Enter the number of queries: ";
cin >> queries;
while (queries--) {
cout << "Enter range (left and right): ";
cin >> left >> right;
cout << "Minimum in range [" << left << ", " << right << "] is: " << seg_tree.range_minimum_query(left, right) << endl;
}
return 0;
}
Output:
4. Count the Number of Elements in a Range Greater Than a Given Value
This program implements a segment tree to count the number of elements in a specified range greater than a given value. It initializes the segment tree based on whether elements are greater than 0. Queries recursively calculate the count of elements greater than the specified value in a given range by summing the results from child nodes.
Code:
#include <iostream>
using namespace std;
#define MAX 1000
class SegmentTree {
private:
int segment_tree[4 * MAX];
int arr[MAX];
int n;
// Build the segment tree
void build_tree(int node, int start, int end) {
if (start == end) {
segment_tree[node] = (arr[start] > 0) ? 1 : 0;
} else {
int mid = (start + end) / 2;
int left_child = 2 * node + 1;
int right_child = 2 * node + 2;
build_tree(left_child, start, mid);
build_tree(right_child, mid + 1, end);
segment_tree[node] = segment_tree[left_child] + segment_tree[right_child];
}
}
// Query the segment tree
int query_tree(int node, int start, int end, int l, int r, int value) {
if (start > r || end < l) {
return 0; // Out of range
}
if (start >= l && end <= r) {
return count_greater(node, start, end, value);
}
int mid = (start + end) / 2;
int left_child = 2 * node + 1;
int right_child = 2 * node + 2;
int left_result = query_tree(left_child, start, mid, l, r, value);
int right_result = query_tree(right_child, mid + 1, end, l, r, value);
return left_result + right_result;
}
// Count numbers greater than value in a range
int count_greater(int node, int start, int end, int value) {
if (start == end) {
return (arr[start] > value) ? 1 : 0;
}
int mid = (start + end) / 2;
int left_child = 2 * node + 1;
int right_child = 2 * node + 2;
return count_greater(left_child, start, mid, value) + count_greater(right_child, mid + 1, end, value);
}
public:
SegmentTree(int input_arr[], int size) {
n = size;
for (int i = 0; i < n; i++) {
arr[i] = input_arr[i];
}
build_tree(0, 0, n - 1);
}
int query(int l, int r, int value) {
return query_tree(0, 0, n - 1, l, r, value);
}
};
int main() {
int arr[] = {1, 5, 2, 8, 6, 3};
int n = 6;
SegmentTree segment_tree(arr, n);
int l, r, value;
cout << "Enter range (l r) and value: ";
cin >> l >> r >> value;
cout << "Number of elements greater than " << value << " in range (" << l << ", " << r << "): ";
cout << segment_tree.query(l, r, value) << endl;
return 0;
}
Output:
5. Solve the "range XOR query" problem using a segment tree.
This program implements the range XOR query using a segment tree. The build function constructs the tree by combining XOR values of child nodes recursively. The query function calculates the XOR of elements in the given range using the segment tree. It handles three cases: no overlap, partial overlap, and complete overlap. The range_xor function is a public interface to query the range XOR.
Code:
#include <iostream>
#include <cstring>
using namespace std;
#define MAX 1000
class Segment_Tree {
private:
int segment_tree[4 * MAX]; // Segment tree array
int array[MAX]; // Input array
int size; // Size of the input array
// Build the segment tree
void build(int node, int start, int end) {
if (start == end) {
segment_tree[node] = array[start];
} else {
int mid = (start + end) / 2;
build(2 * node, start, mid);
build(2 * node + 1, mid + 1, end);
segment_tree[node] = segment_tree[2 * node] ^ segment_tree[2 * node + 1];
}
}
// Query the XOR for a range
int query(int node, int start, int end, int left, int right) {
if (right < start || left > end) {
return 0; // No overlap
}
if (left <= start && end <= right) {
return segment_tree[node]; // Complete overlap
}
int mid = (start + end) / 2;
int left_xor = query(2 * node, start, mid, left, right);
int right_xor = query(2 * node + 1, mid + 1, end, left, right);
return left_xor ^ right_xor; // Partial overlap
}
public:
// Initialize the segment tree
void initialize(int arr[], int n) {
size = n;
memcpy(array, arr, n * sizeof(int));
build(1, 0, n - 1);
}
// Public function to query the range XOR
int range_xor(int left, int right) {
return query(1, 0, size - 1, left, right);
}
};
int main() {
int n;
cout << "Enter the size of the array: ";
cin >> n;
int arr[MAX];
cout << "Enter the elements of the array: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
Segment_Tree seg_tree;
seg_tree.initialize(arr, n);
int queries;
cout << "Enter the number of queries: ";
cin >> queries;
while (queries--) {
int left, right;
cout << "Enter the range (0-based index): ";
cin >> left >> right;
cout << "Range XOR (" << left << ", " << right << "): " << seg_tree.range_xor(left, right) << endl;
}
return 0;
}
Output:
Day 33 highlighted the efficiency and versatility of segment trees in handling range queries and updates. From computing sums and minimums to solving advanced problems like range XOR and conditional counts, these exercises showcased the importance of mastering this fundamental data structure for competitive programming and real-world applications. 🚀