Segment Trees
Master segment trees for efficient range queries and updates. Learn construction, point/range updates, lazy propagation, and advanced applications in competitive programming.
1. Basic Segment Tree
Segment tree for range sum queries and point updates with O(log n) complexity.
Basic Segment Tree Implementation
#include <iostream>
#include <vector>
using namespace std;
class SegmentTree {
private:
vector<long long> tree;
int n;
void build(vector<int>& arr, int node, int start, int end) {
if (start == end) {
tree[node] = arr[start];
} else {
int mid = (start + end) / 2;
build(arr, 2*node, start, mid);
build(arr, 2*node+1, mid+1, end);
tree[node] = tree[2*node] + tree[2*node+1];
}
}
void updateHelper(int node, int start, int end, int idx, int val) {
if (start == end) {
tree[node] = val;
} else {
int mid = (start + end) / 2;
if (idx <= mid) {
updateHelper(2*node, start, mid, idx, val);
} else {
updateHelper(2*node+1, mid+1, end, idx, val);
}
tree[node] = tree[2*node] + tree[2*node+1];
}
}
long long queryHelper(int node, int start, int end, int l, int r) {
if (r < start || end < l) {
return 0; // Outside range
}
if (l <= start && end <= r) {
return tree[node]; // Complete overlap
}
int mid = (start + end) / 2;
long long p1 = queryHelper(2*node, start, mid, l, r);
long long p2 = queryHelper(2*node+1, mid+1, end, l, r);
return p1 + p2;
}
public:
SegmentTree(vector<int>& arr) {
n = arr.size();
tree.resize(4 * n);
build(arr, 1, 0, n-1);
}
void update(int idx, int val) {
updateHelper(1, 0, n-1, idx, val);
}
long long query(int l, int r) {
return queryHelper(1, 0, n-1, l, r);
}
};
int main() {
vector<int> arr = {1, 3, 5, 7, 9, 11};
SegmentTree st(arr);
cout << "Original array: ";
for (int x : arr) cout << x << " ";
cout << endl;
// Range queries
cout << "Sum of range [1, 3]: " << st.query(1, 3) << endl;
cout << "Sum of range [2, 5]: " << st.query(2, 5) << endl;
// Point update
st.update(1, 10);
cout << "After updating index 1 to 10:" << endl;
cout << "Sum of range [1, 3]: " << st.query(1, 3) << endl;
cout << "Sum of range [0, 5]: " << st.query(0, 5) << endl;
return 0;
}2. Lazy Propagation
Lazy propagation for efficient range updates in O(log n) time complexity.
Segment Tree with Lazy Propagation
#include <iostream>
#include <vector>
using namespace std;
class LazySegmentTree {
private:
vector<long long> tree, lazy;
int n;
void build(vector<int>& arr, int node, int start, int end) {
if (start == end) {
tree[node] = arr[start];
} else {
int mid = (start + end) / 2;
build(arr, 2*node, start, mid);
build(arr, 2*node+1, mid+1, end);
tree[node] = tree[2*node] + tree[2*node+1];
}
}
void updateLazy(int node, int start, int end) {
if (lazy[node] != 0) {
tree[node] += lazy[node] * (end - start + 1);
if (start != end) {
lazy[2*node] += lazy[node];
lazy[2*node+1] += lazy[node];
}
lazy[node] = 0;
}
}
void updateRange(int node, int start, int end, int l, int r, int val) {
updateLazy(node, start, end);
if (start > r || end < l) {
return;
}
if (start >= l && end <= r) {
tree[node] += val * (end - start + 1);
if (start != end) {
lazy[2*node] += val;
lazy[2*node+1] += val;
}
return;
}
int mid = (start + end) / 2;
updateRange(2*node, start, mid, l, r, val);
updateRange(2*node+1, mid+1, end, l, r, val);
updateLazy(2*node, start, mid);
updateLazy(2*node+1, mid+1, end);
tree[node] = tree[2*node] + tree[2*node+1];
}
long long queryRange(int node, int start, int end, int l, int r) {
if (start > r || end < l) {
return 0;
}
updateLazy(node, start, end);
if (start >= l && end <= r) {
return tree[node];
}
int mid = (start + end) / 2;
long long p1 = queryRange(2*node, start, mid, l, r);
long long p2 = queryRange(2*node+1, mid+1, end, l, r);
return p1 + p2;
}
public:
LazySegmentTree(vector<int>& arr) {
n = arr.size();
tree.resize(4 * n);
lazy.resize(4 * n);
build(arr, 1, 0, n-1);
}
void update(int l, int r, int val) {
updateRange(1, 0, n-1, l, r, val);
}
long long query(int l, int r) {
return queryRange(1, 0, n-1, l, r);
}
};
int main() {
vector<int> arr = {1, 3, 5, 7, 9, 11};
LazySegmentTree lst(arr);
cout << "Original array: ";
for (int x : arr) cout << x << " ";
cout << endl;
cout << "Sum of range [1, 3]: " << lst.query(1, 3) << endl;
// Range update: add 10 to range [1, 3]
lst.update(1, 3, 10);
cout << "After adding 10 to range [1, 3]:" << endl;
cout << "Sum of range [1, 3]: " << lst.query(1, 3) << endl;
cout << "Sum of range [0, 5]: " << lst.query(0, 5) << endl;
// Another range update
lst.update(2, 4, 5);
cout << "After adding 5 to range [2, 4]:" << endl;
cout << "Sum of range [2, 4]: " << lst.query(2, 4) << endl;
return 0;
}3. Advanced Applications
Advanced segment tree applications including range minimum/maximum queries and coordinate compression.
Range Minimum Query (RMQ) Segment Tree
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
class RMQSegmentTree {
private:
vector<int> tree;
int n;
void build(vector<int>& arr, int node, int start, int end) {
if (start == end) {
tree[node] = arr[start];
} else {
int mid = (start + end) / 2;
build(arr, 2*node, start, mid);
build(arr, 2*node+1, mid+1, end);
tree[node] = min(tree[2*node], tree[2*node+1]);
}
}
void updateHelper(int node, int start, int end, int idx, int val) {
if (start == end) {
tree[node] = val;
} else {
int mid = (start + end) / 2;
if (idx <= mid) {
updateHelper(2*node, start, mid, idx, val);
} else {
updateHelper(2*node+1, mid+1, end, idx, val);
}
tree[node] = min(tree[2*node], tree[2*node+1]);
}
}
int queryHelper(int node, int start, int end, int l, int r) {
if (r < start || end < l) {
return INT_MAX;
}
if (l <= start && end <= r) {
return tree[node];
}
int mid = (start + end) / 2;
int p1 = queryHelper(2*node, start, mid, l, r);
int p2 = queryHelper(2*node+1, mid+1, end, l, r);
return min(p1, p2);
}
public:
RMQSegmentTree(vector<int>& arr) {
n = arr.size();
tree.resize(4 * n);
build(arr, 1, 0, n-1);
}
void update(int idx, int val) {
updateHelper(1, 0, n-1, idx, val);
}
int query(int l, int r) {
return queryHelper(1, 0, n-1, l, r);
}
};
int main() {
vector<int> arr = {1, 3, 2, 7, 9, 11};
RMQSegmentTree rmq(arr);
cout << "Array: ";
for (int x : arr) cout << x << " ";
cout << endl;
cout << "RMQ(1, 3): " << rmq.query(1, 3) << endl;
cout << "RMQ(2, 5): " << rmq.query(2, 5) << endl;
cout << "RMQ(0, 5): " << rmq.query(0, 5) << endl;
rmq.update(2, 0);
cout << "After updating index 2 to 0:" << endl;
cout << "RMQ(1, 3): " << rmq.query(1, 3) << endl;
cout << "RMQ(0, 5): " << rmq.query(0, 5) << endl;
return 0;
}Summary
- Basic Segment Tree: Efficient range queries and point updates in O(log n)
- Lazy Propagation: Range updates with deferred computation for optimization
- Range Minimum/Maximum: Adaptable to different associative operations
- Applications: Range sum, RMQ, coordinate compression, and interval problems
- Space Complexity: O(4n) space for storing the tree structure