Segment Tree Concept
A segment tree stores aggregate values (sum/min/max) for each segment [l,r] in a binary tree. Leaf nodes = individual elements. Internal nodes = aggregate of children.
[0,5]=21
/ \
[0,2]=6 [3,5]=15
/ \ / \
[0,1]=3 [2]=3 [3,4]=9 [5]=6
/ \ / \
[0]=1 [1]=2 [3]=4 [4]=5
Build: O(n)
Query: O(log n)
Update: O(log n)
Standard Segment Tree (Sum)
C++
class SegTree {
int n;
vector<int> tree;
public:
SegTree(vector<int>& nums) : n(nums.size()), tree(4*nums.size()) {
build(nums, 1, 0, n-1);
}
void build(vector<int>& a, int node, int l, int r) {
if(l==r) { tree[node]=a[l]; return; }
int m=(l+r)/2;
build(a,2*node,l,m); build(a,2*node+1,m+1,r);
tree[node]=tree[2*node]+tree[2*node+1];
}
void update(int pos, int val, int node=1, int l=0, int r=-1) {
if(r==-1) r=n-1;
if(l==r) { tree[node]=val; return; }
int m=(l+r)/2;
if(pos<=m) update(pos,val,2*node,l,m);
else update(pos,val,2*node+1,m+1,r);
tree[node]=tree[2*node]+tree[2*node+1];
}
int query(int ql, int qr, int node=1, int l=0, int r=-1) {
if(r==-1) r=n-1;
if(ql>r || qr<l) return 0; // out of range
if(ql<=l && r<=qr) return tree[node]; // fully covered
int m=(l+r)/2;
return query(ql,qr,2*node,l,m)+query(ql,qr,2*node+1,m+1,r);
}
};
// Build: O(n) Query/Update: O(log n) Space: O(n)
BIT (Fenwick Tree) — Simpler for Prefix Sums
Binary Indexed Tree (BIT/Fenwick Tree) is simpler to code than segment tree when you only need prefix sums with point updates. O(log n) both operations, O(n) space.
C++
struct BIT {
int n;
vector<int> tree;
BIT(int n) : n(n), tree(n+1,0) {}
void update(int i, int delta) {
for(i++; i<=n; i+=i&(-i)) tree[i]+=delta;
}
int query(int i) { // prefix sum [0..i]
int s=0;
for(i++; i>0; i-=i&(-i)) s+=tree[i];
return s;
}
int rangeQuery(int l, int r) { return query(r) - (l>0?query(l-1):0); }
};
// Use when: point updates + prefix/range sum queries only
// Segment tree when: range updates, min/max, more complex aggregates
Interactive: Range Sum Query + Point Update
Array [1,2,3,4,5,6]. Watch how a range query [2..4] touches only O(log n) nodes, then see a point update propagate up the tree.
Practice Problems
#303Range Sum Query — ImmutableEasy
Answer sumRange(l, r) queries on an array that never changes.
Pattern: No tree needed! Static data → prefix sums: sum(l,r) = pre[r+1] − pre[l]. Reach for a segment tree only when updates arrive. Knowing when NOT to use the heavy tool is the real lesson.
C++
class NumArray {
vector<long long> pre;
public:
NumArray(vector<int>& nums) : pre(nums.size()+1, 0) {
for(int i=0;i<nums.size();i++) pre[i+1]=pre[i]+nums[i];
}
int sumRange(int l, int r) { return pre[r+1]-pre[l]; }
};
// Build: O(n) Query: O(1) — beats any tree for static data
#307Range Sum Query — MutableMedium
Support both update(i, val) and sumRange(l, r) operations efficiently.
Pattern: Segment tree or BIT. BIT is simpler here: prefix sum queries with point updates.
C++
class NumArray {
BIT bit;
vector<int> nums;
public:
NumArray(vector<int>& nums) : bit(nums.size()), nums(nums) {
for(int i=0;i<nums.size();i++) bit.update(i,nums[i]);
}
void update(int i, int val) {
bit.update(i, val-nums[i]); // add delta
nums[i]=val;
}
int sumRange(int l, int r) { return bit.rangeQuery(l,r); }
};
// Each op: O(log n) Space: O(n)
#715Range ModuleHard
Track ranges of numbers: addRange, removeRange, and queryRange (is [l,r) fully tracked?).
Pattern: Ordered map of disjoint intervals — a "segment set". Each op finds neighbors with lower_bound, then merges/splits. A lazily-propagated segment tree over coordinates also works, but the interval map is the interview-friendly answer.
C++
class RangeModule {
map<int,int> iv; // start → end, disjoint, sorted
public:
void addRange(int l, int r) {
auto it = iv.upper_bound(l);
if(it!=iv.begin() && prev(it)->second >= l) { --it; l=it->first; }
while(it!=iv.end() && it->first <= r) { r=max(r,it->second); it=iv.erase(it); }
iv[l]=r;
}
bool queryRange(int l, int r) {
auto it = iv.upper_bound(l);
return it!=iv.begin() && prev(it)->second >= r;
}
void removeRange(int l, int r) {
auto it = iv.upper_bound(l);
if(it!=iv.begin() && prev(it)->second > l) {
--it;
int e=it->second;
if(it->first < l) it->second=l; else it=iv.erase(it);
if(e > r) iv[r]=e;
if(it!=iv.end() && it->first<l) ++it;
}
while(it!=iv.end() && it->first < r) {
if(it->second > r) { iv[r]=it->second; iv.erase(it); break; }
it=iv.erase(it);
}
}
};
// Each op: O(log n) amortized — every interval inserted/erased once
#327Count of Range SumHard
Count range sums S(i,j) that lie within [lower, upper].
Pattern: Prefix sums + count "how many earlier prefixes fall in [pre−upper, pre−lower]". That's an order-statistics query → coordinate-compress prefix sums into a BIT/segment tree, or count during merge sort.
C++
int countRangeSum(vector<int>& nums, int lower, int upper) {
int n=nums.size();
vector<long long> pre(n+1,0);
for(int i=0;i<n;i++) pre[i+1]=pre[i]+nums[i];
// merge-sort count: pairs (i<j) with lower ≤ pre[j]-pre[i] ≤ upper
function<int(int,int)> go = [&](int l, int r) -> int {
if(r-l<=1) return 0;
int m=(l+r)/2, cnt=go(l,m)+go(m,r);
int lo=m, hi=m;
for(int i=l;i<m;i++) {
while(lo<r && pre[lo]-pre[i] < lower) lo++;
while(hi<r && pre[hi]-pre[i] <= upper) hi++;
cnt += hi-lo;
}
inplace_merge(pre.begin()+l, pre.begin()+m, pre.begin()+r);
return cnt;
};
return go(0, n+1);
}
// Time: O(n log n) Space: O(n)
#493Reverse PairsHard
Count pairs (i,j) where i < j and nums[i] > 2 * nums[j]. Important: the 2x factor.
Pattern: Modified merge sort. During merge, count how many elements in right half satisfy nums[j]*2 < nums[i] for each i in left half. Two-pointer count step before merging.
C++
int mergeCount(vector<int>& a, int l, int r) {
if(r-l<=1) return 0;
int m=(l+r)/2;
int cnt=mergeCount(a,l,m)+mergeCount(a,m,r);
int j=m;
for(int i=l;i<m;i++) {
while(j<r && (long)a[i]>2L*a[j]) j++;
cnt+=j-m;
}
inplace_merge(a.begin()+l,a.begin()+m,a.begin()+r);
return cnt;
}
int reversePairs(vector<int>& nums) {
return mergeCount(nums, 0, nums.size());
}
// Time: O(n log n) Space: O(log n)
When to use: Segment tree when you need range queries (sum/min/max) AND updates. If only prefix sums + point updates → BIT (simpler). If only static queries → prefix sum array (simplest).
Deeper Understanding
🧠 Under the Hood — the tree lives in a flat array
Like a binary heap, the segment tree needs no pointer chasing — the structure is implicit in the indices. A node covering [l..r] has children covering [l..mid] and [mid+1..r]; the key theorem is that any query range decomposes into at most 2 nodes per level, which is where O(log n) per query comes from. Every range-query data structure (BIT, sparse table, sqrt blocks) is a different trade-off on this same decomposition idea.
⚖️ When to Use / When NOT to Use
✅ Use when you mix point/range updates with range queries (sum, min, max, gcd)
O(log n) for both — the only general tool that does updates + arbitrary-range aggregates.
✅ Use when the aggregate isn't invertible (min/max) but ranges are queried
BITs need subtraction (prefix trick); min/max can't be subtracted, segment trees don't care.
❌ Avoid when data is static
Instead: prefix sums (O(1) sum queries) or a sparse table (O(1) min/max) — far less code.
❌ Avoid when you only need prefix sums with point updates
Instead: a Fenwick/BIT — 10 lines, half the memory, same O(log n).
🚫 Common Misconceptions
"A segment tree always needs 4n memory"
The recursive version allocates 4n to be safe, but the iterative bottom-up variant uses exactly 2n — and for n a power of two the tree is perfect.
"Segment tree = interval tree"
Different structures: a segment tree indexes array positions for aggregates; an interval tree stores a set of intervals to find which contain a point. Interviewers do distinguish them.
"Range updates need rebuilding"
Lazy propagation defers the update: mark the covering node, push the mark down only when a later query passes through. Range update becomes O(log n) too.
🎤 Interview Follow-ups
"Explain lazy propagation in one minute"
When an update fully covers a node's range, update its aggregate, stamp a pending delta on the node, and stop. Any traversal that later visits its children first pushes the delta down one level. Each op still touches O(log n) nodes.
"Fenwick vs segment tree — how do you choose?"
Fenwick: shorter code, 2× less memory, prefix-invertible ops only (sum, xor). Segment tree: any associative op, range updates via laziness, easier to extend (k-th order statistic, walk on tree). Say Fenwick first if the op is a sum.
"When is sqrt decomposition good enough?"
n ≤ ~10⁵ with loose limits, or when the operation doesn't compose associatively (e.g. \"count distinct in range\" via Mo's algorithm). O(√n) per query but trivial to reason about and modify.
🎓 Phase 4 Complete!
You've mastered 6 advanced techniques: Two Pointers, Sliding Window, Monotonic Stack, Tries, Bit Manipulation, and Segment Trees. You're now ready for Phase 5: LeetCode Hard mastery.