Segment Tree Fundamentals
What is a Segment Tree?
A Segment Tree is a binary tree data structure used for storing information about intervals/segments. It allows efficient:
- Range queries: Sum, min, max, gcd over a range
- Point updates: Update a single element
Both operations in O(log n) time.
Tree Structure
For array [1, 3, 5, 7, 9, 11]:
Segment Tree for Range Sum:
[1-6, 36]
/ \
[1-3, 9] [4-6, 25]
/ \\ / \
[1-2, 4] [3-3, 5] [4-5, 16] [6-6, 11]
/ \\ \\ / \\ \
[1-1,1][2-2,3] [3-3,5] [4-4,7][5-5,9] [6-6,11]
Implementation
public class SegmentTree {
private int[] tree;
private int n;
public SegmentTree(int[] nums) {
n = nums.length;
tree = new int[4 * n]; // 4n is safe upper bound
build(nums, 1, 0, n - 1);
}
private void build(int[] nums, int node, int start, int end) {
if (start == end) {
tree[node] = nums[start];
} else {
int mid = start + (end - start) / 2;
build(nums, 2 * node, start, mid);
build(nums, 2 * node + 1, mid + 1, end);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
}
public void update(int index, int val) {
update(1, 0, n - 1, index, val);
}
private void update(int node, int start, int end, int idx, int val) {
if (start == end) {
tree[node] = val;
} else {
int mid = start + (end - start) / 2;
if (idx <= mid) {
update(2 * node, start, mid, idx, val);
} else {
update(2 * node + 1, mid + 1, end, idx, val);
}
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
}
public int query(int left, int right) {
return query(1, 0, n - 1, left, right);
}
private int query(int node, int start, int end, int l, int r) {
if (r < start || end < l) return 0; // No overlap
if (l <= start && end <= r) return tree[node]; // Complete overlap
int mid = start + (end - start) / 2;
int leftSum = query(2 * node, start, mid, l, r);
int rightSum = query(2 * node + 1, mid + 1, end, l, r);
return leftSum + rightSum;
}
}
Time Complexity
- Build: O(n)
- Update: O(log n)
- Query: O(log n)
- Space: O(n)
Lazy Propagation for Range Updates
Lazy Propagation
Lazy propagation allows efficient range updates (e.g., add value to all elements in a range) in O(log n) time.
Key Idea
Instead of updating all nodes immediately, mark nodes as "lazy" and push updates down when needed.
Implementation for Range Add + Range Sum
public class LazySegmentTree {
private int[] tree;
private int[] lazy;
private int n;
public LazySegmentTree(int[] nums) {
n = nums.length;
tree = new int[4 * n];
lazy = new int[4 * n];
build(nums, 1, 0, n - 1);
}
private void build(int[] nums, int node, int start, int end) {
if (start == end) {
tree[node] = nums[start];
} else {
int mid = start + (end - start) / 2;
build(nums, 2 * node, start, mid);
build(nums, 2 * node + 1, mid + 1, end);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
}
private void pushDown(int node, int start, int end) {
if (lazy[node] != 0) {
int mid = start + (end - start) / 2;
// Apply to left child
tree[2 * node] += lazy[node] * (mid - start + 1);
lazy[2 * node] += lazy[node];
// Apply to right child
tree[2 * node + 1] += lazy[node] * (end - mid);
lazy[2 * node + 1] += lazy[node];
lazy[node] = 0;
}
}
public void rangeUpdate(int l, int r, int val) {
rangeUpdate(1, 0, n - 1, l, r, val);
}
private void rangeUpdate(int node, int start, int end, int l, int r, int val) {
if (r < start || end < l) return;
if (l <= start && end <= r) {
tree[node] += val * (end - start + 1);
lazy[node] += val;
return;
}
pushDown(node, start, end);
int mid = start + (end - start) / 2;
rangeUpdate(2 * node, start, mid, l, r, val);
rangeUpdate(2 * node + 1, mid + 1, end, l, r, val);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
public int rangeQuery(int l, int r) {
return rangeQuery(1, 0, n - 1, l, r);
}
private int rangeQuery(int node, int start, int end, int l, int r) {
if (r < start || end < l) return 0;
if (l <= start && end <= r) return tree[node];
pushDown(node, start, end);
int mid = start + (end - start) / 2;
return rangeQuery(2 * node, start, mid, l, r) +
rangeQuery(2 * node + 1, mid + 1, end, l, r);
}
}
When to Use Lazy Propagation
- Range add/subtract + Range sum/min/max
- Range set + Range query
- Multiple types of updates combined
Practice Problems
Given an integer array nums, handle multiple queries of the following types: Update the value of an element in nums. Calculate the sum of elements of nums between indices left and right inclusive.
Example:
Input: nums = [1,3,5], update(1,2), sumRange(0,2)
Output: 8
After update: [1,2,5], sum = 1+2+5 = 8
Solution
```java
class NumArray {
private SegmentTree segTree;
public NumArray(int[] nums) {
segTree = new SegmentTree(nums);
}
public void update(int index, int val) {
segTree.update(index, val);
}
public int sumRange(int left, int right) {
return segTree.query(left, right);
}
}
```Edge Cases:
- Single element array
- Update same index multiple times
- Query entire array
- Query single element
Quiz
1. What is the space complexity of a Segment Tree for an array of size n?
2. Why do we use lazy propagation in Segment Trees?
3. What is the primary purpose of Segment Tree?
4. What is a common mistake when implementing Segment Tree?
Flashcards
Question
What is the time complexity for build, update, and query in a Segment Tree?
Click to reveal answer
Answer
Build: O(n), Update: O(log n), Query: O(log n). Segment Tree provides logarithmic time for both updates and queries.
Question
When should you use Segment Tree over Fenwick Tree?
Click to reveal answer
Answer
Use Segment Tree when you need: 1) Range min/max queries, 2) Multiple types of queries, 3) More flexibility with arbitrary operations. Fenwick Tree is simpler for sum queries.
Question
What is Segment Tree?
Click to reveal answer
Answer
Segment Tree is a key concept in software engineering.
Question
When to use Segment Tree?
Click to reveal answer
Answer
Use Segment Tree when building production systems that require reliability, scalability, and maintainability.
Question
Segment Tree best practices
Click to reveal answer
Answer
Follow SOLID principles, write clean code, test thoroughly, document decisions, and monitor in production.
Revision Notes
Key Takeaways
- 1.Segment Tree provides O(log n) for both point updates and range queries
- 2.Build time is O(n), space is O(4n)
- 3.Lazy propagation enables O(log n) range updates
- 4.Useful for problems with multiple range query/update operations
- 5.More flexible than Fenwick Tree but harder to implement
Interview Tips
- •Start with a simple implementation before adding lazy propagation
- •Use 4*n array size to avoid index out of bounds
- •For range updates, always propagate laziness before querying children
- •Practice: Range Sum Query Mutable, Range Minimum Query, Count of Smaller Numbers After Self
- •Know when to use Segment Tree vs Fenwick Tree vs Sparse Table
Cheat Sheet
Segment Tree Cheat Sheet
Basic Structure
void build(int[] nums, int node, int start, int end) {
if (start == end) { tree[node] = nums[start]; return; }
int mid = (start + end) / 2;
build(nums, 2*node, start, mid);
build(nums, 2*node+1, mid+1, end);
tree[node] = tree[2*node] + tree[2*node+1];
}
Query (Range Sum)
int query(int node, int start, int end, int l, int r) {
if (r < start || end < l) return 0;
if (l <= start && end <= r) return tree[node];
int mid = (start + end) / 2;
return query(2*node, start, mid, l, r) +
query(2*node+1, mid+1, end, l, r);
}
Key Points
- Array size: 4n (safe upper bound)
- Root is at index 1
- Left child: 2node, Right child: 2node+1
- Use lazy[] array for range updates
Applications
- Range sum/min/max queries
- Range updates with lazy propagation
- Count inversions in merge sort
- Interval scheduling problems