Chapter Goal: Master the two most powerful range-query data structures in competitive programming and advanced FAANG interviews. Both structures solve the same core problem — answer repeated range queries on a mutable array in O(log n) — but with different trade-offs in flexibility and implementation complexity. By the end of this chapter you will implement both from scratch with confidence.
You have an array of n elements. You need to answer multiple queries of the form "what is the sum/min/max of elements from index l to r?" AND update individual elements between queries.
Naive approach:
Query [l, r]: O(n) scan → n queries → O(n²) total ← Too slow for n = 10⁵
With Segment Tree or Fenwick Tree:
Query [l, r]: O(log n)
Update index i: O(log n)
n queries + n updates: O(n log n) ← Fast enough
Static array (no updates)?
→ Use Prefix Sum for O(1) range sum queries (Chapter 4)
→ Use Sparse Table for O(1) range min/max queries
Mutable array + range queries?
→ Use Fenwick Tree (simpler) for point update + range sum
→ Use Segment Tree (more powerful) for everything else
Range UPDATES (update a range, not just one element)?
→ Use Segment Tree with Lazy Propagation
→ Or use Difference Array for O(1) range add + O(n) rebuild
| Operation | Prefix Sum | Fenwick Tree | Segment Tree | Seg Tree + Lazy |
|---|---|---|---|---|
| Point update | O(n) | O(log n) | O(log n) | O(log n) |
| Range update (add) | O(1) + O(n) rebuild | O(log n) | O(log n) | O(log n) |
| Range query (sum) | O(1) | O(log n) | O(log n) | O(log n) |
| Range query (min/max) | O(n) | No | O(log n) | O(log n) |
| Range query (GCD/XOR) | No | No | O(log n) | O(log n) |
A segment tree is a binary tree where:
Array: [2, 1, 5, 3, 4] (0-indexed)
Segment Tree (sum):
[15, 0-4]
/ \
[8, 0-2] [7, 3-4]
/ \ / \
[3, 0-1] [5,2] [3,3] [4,4]
/ \
[2,0] [1,1]
Array representation (1-indexed, size = 4n):
tree[1] = 15 (range [0,4])
tree[2] = 8 (range [0,2])
tree[3] = 7 (range [3,4])
tree[4] = 3 (range [0,1])
tree[5] = 5 (range [2,2])
tree[6] = 3 (range [3,3])
tree[7] = 4 (range [4,4])
tree[8] = 2 (range [0,0])
tree[9] = 1 (range [1,1])
For node at index i:
Left child: 2*i
Right child: 2*i + 1
Parent: i/2
class SegmentTree {
int n;
vector<long long> tree;
void build(vector<int>& arr, int node, int l, int r) {
if (l == r) {
tree[node] = arr[l];
return;
}
int mid = l + (r - l) / 2;
build(arr, 2*node, l, mid);
build(arr, 2*node+1, mid+1, r);
tree[node] = tree[2*node] + tree[2*node+1]; // Merge children
}
void update(int node, int l, int r, int pos, int val) {
if (l == r) { tree[node] = val; return; }
int mid = l + (r - l) / 2;
if (pos <= mid) update(2*node, l, mid, pos, val);
else update(2*node+1, mid+1, r, pos, val);
tree[node] = tree[2*node] + tree[2*node+1]; // Re-merge after update
}
long long query(int node, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return 0; // Out of range → identity (0 for sum)
if (ql <= l && r <= qr) return tree[node]; // Fully inside → return node value
int mid = l + (r - l) / 2;
return query(2*node, l, mid, ql, qr)
+ query(2*node+1, mid+1, r, ql, qr);
}
public:
SegmentTree(vector<int>& arr) : n(arr.size()), tree(4*arr.size(), 0) {
build(arr, 1, 0, n-1);
}
void update(int pos, int val) { update(1, 0, n-1, pos, val); }
long long query(int l, int r) { return query(1, 0, n-1, l, r); }
};
// Build: O(n), Update: O(log n), Query: O(log n)
// Space: O(4n) — always allocate 4x the array size to be safeclass RMQTree {
int n;
vector<int> tree;
void build(vector<int>& arr, int node, int l, int r) {
if (l == r) { tree[node] = arr[l]; return; }
int mid = l + (r-l)/2;
build(arr, 2*node, l, mid);
build(arr, 2*node+1, mid+1, r);
tree[node] = min(tree[2*node], tree[2*node+1]); // Merge: take minimum
}
void update(int node, int l, int r, int pos, int val) {
if (l == r) { tree[node] = val; return; }
int mid = l + (r-l)/2;
if (pos <= mid) update(2*node, l, mid, pos, val);
else update(2*node+1, mid+1, r, pos, val);
tree[node] = min(tree[2*node], tree[2*node+1]);
}
int query(int node, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return INT_MAX; // Identity for min
if (ql <= l && r <= qr) return tree[node];
int mid = l + (r-l)/2;
return min(query(2*node, l, mid, ql, qr),
query(2*node+1, mid+1, r, ql, qr));
}
public:
RMQTree(vector<int>& arr) : n(arr.size()), tree(4*n) { build(arr, 1, 0, n-1); }
void update(int pos, int val) { update(1, 0, n-1, pos, val); }
int query(int l, int r) { return query(1, 0, n-1, l, r); }
};
// Build: O(n), Update/Query: O(log n)
// Change min() to max() for range max, to gcd() for range GCD, etc.template<typename T>
class GenericSegTree {
int n;
vector<T> tree;
T identity;
function<T(T, T)> merge; // Associative merge function
void build(vector<T>& arr, int node, int l, int r) {
if (l == r) { tree[node] = arr[l]; return; }
int mid = l + (r-l)/2;
build(arr, 2*node, l, mid);
build(arr, 2*node+1, mid+1, r);
tree[node] = merge(tree[2*node], tree[2*node+1]);
}
void update(int node, int l, int r, int pos, T val) {
if (l == r) { tree[node] = val; return; }
int mid = l + (r-l)/2;
if (pos <= mid) update(2*node, l, mid, pos, val);
else update(2*node+1, mid+1, r, pos, val);
tree[node] = merge(tree[2*node], tree[2*node+1]);
}
T query(int node, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return identity;
if (ql <= l && r <= qr) return tree[node];
int mid = l + (r-l)/2;
return merge(query(2*node, l, mid, ql, qr),
query(2*node+1, mid+1, r, ql, qr));
}
public:
GenericSegTree(vector<T>& arr, T identity, function<T(T,T)> merge)
: n(arr.size()), tree(4*arr.size(), identity),
identity(identity), merge(merge) {
build(arr, 1, 0, n-1);
}
void update(int pos, T val) { update(1, 0, n-1, pos, val); }
T query(int l, int r) { return query(1, 0, n-1, l, r); }
};
// Usage examples:
// Sum: GenericSegTree<long long>(arr, 0LL, [](auto a, auto b){ return a+b; })
// Min: GenericSegTree<int>(arr, INT_MAX, [](auto a, auto b){ return min(a,b); })
// GCD: GenericSegTree<int>(arr, 0, [](auto a, auto b){ return __gcd(a,b); })
// XOR: GenericSegTree<int>(arr, 0, [](auto a, auto b){ return a^b; })class SegTreeIterative {
int n;
vector<long long> tree;
public:
SegTreeIterative(int n) : n(n), tree(2*n, 0) {}
// Build from array: set leaves then build upward
void build(vector<int>& arr) {
for (int i = 0; i < n; i++) tree[n+i] = arr[i];
for (int i = n-1; i >= 1; i--) tree[i] = tree[2*i] + tree[2*i+1];
}
// Point update at position pos (0-indexed)
void update(int pos, long long val) {
pos += n;
tree[pos] = val;
for (pos >>= 1; pos >= 1; pos >>= 1)
tree[pos] = tree[2*pos] + tree[2*pos+1];
}
// Range sum query [l, r] (0-indexed, inclusive)
long long query(int l, int r) {
long long res = 0;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) res += tree[l++];
if (r & 1) res += tree[--r];
}
return res;
}
};
// Space: O(2n) — more memory-efficient than 4n recursive version
// Update/Query: O(log n) with smaller constant factorRange updates (e.g., "add 5 to all elements from index 2 to 7") applied naively update O(n) leaves and O(n log n) total nodes. Lazy propagation defers these updates to achieve O(log n).
Instead of immediately updating all affected nodes, attach a lazy tag to each node. When we later visit that node for a query or another update, we first push down the lazy tag to its children before processing.
"Add 3 to range [1, 4]" — Lazy approach:
Instead of touching all 4 leaf nodes and their ancestors:
Mark the covering nodes with lazy[node] += 3
When we later query a range that includes a lazy node:
1. Apply the lazy value to the node itself (update tree[node])
2. Push the lazy down to children (lazy[left] += lazy[node], lazy[right] += lazy[node])
3. Clear the lazy at this node (lazy[node] = 0)
4. Proceed with the query/update
class LazySegTree {
int n;
vector<long long> tree, lazy;
// Push pending lazy updates down to children
void pushDown(int node, int l, int r) {
if (lazy[node] == 0) return;
int mid = l + (r-l)/2;
// Apply lazy to left child
tree[2*node] += lazy[node] * (mid - l + 1); // Sum of range increases by lazy * size
lazy[2*node] += lazy[node];
// Apply lazy to right child
tree[2*node+1] += lazy[node] * (r - mid);
lazy[2*node+1] += lazy[node];
lazy[node] = 0; // Clear the current node's lazy
}
void build(vector<int>& arr, int node, int l, int r) {
if (l == r) { tree[node] = arr[l]; return; }
int mid = l + (r-l)/2;
build(arr, 2*node, l, mid);
build(arr, 2*node+1, mid+1, r);
tree[node] = tree[2*node] + tree[2*node+1];
}
// Range update: add val to all elements in [ql, qr]
void rangeUpdate(int node, int l, int r, int ql, int qr, long long val) {
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) {
tree[node] += val * (r - l + 1); // Aggregate update for this node
lazy[node] += val; // Tag children for later
return;
}
pushDown(node, l, r); // Must push before going to children!
int mid = l + (r-l)/2;
rangeUpdate(2*node, l, mid, ql, qr, val);
rangeUpdate(2*node+1, mid+1, r, ql, qr, val);
tree[node] = tree[2*node] + tree[2*node+1];
}
long long rangeQuery(int node, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return 0;
if (ql <= l && r <= qr) return tree[node];
pushDown(node, l, r); // Must push before querying children!
int mid = l + (r-l)/2;
return rangeQuery(2*node, l, mid, ql, qr)
+ rangeQuery(2*node+1, mid+1, r, ql, qr);
}
public:
LazySegTree(vector<int>& arr) : n(arr.size()), tree(4*n, 0), lazy(4*n, 0) {
build(arr, 1, 0, n-1);
}
void update(int l, int r, long long val) { rangeUpdate(1, 0, n-1, l, r, val); }
long long query(int l, int r) { return rangeQuery(1, 0, n-1, l, r); }
void pointUpdate(int pos, int val) { update(pos, pos, val - /* old val */ 0); }
};
// Build: O(n), Range Update: O(log n), Range Query: O(log n)
// Space: O(4n) for tree + O(4n) for lazy// Different lazy type: instead of "add", we "assign"
// lazy[node] = -1 means "no pending assignment"
// lazy[node] = v means "set all elements in this range to v"
void pushDownAssign(int node, int l, int r) {
if (lazy[node] == -1) return;
int mid = l + (r-l)/2;
// Set left child
tree[2*node] = lazy[node] * (mid - l + 1);
lazy[2*node] = lazy[node];
// Set right child
tree[2*node+1] = lazy[node] * (r - mid);
lazy[2*node+1] = lazy[node];
lazy[node] = -1;
}
void rangeAssign(int node, int l, int r, int ql, int qr, long long val) {
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) {
tree[node] = val * (r - l + 1);
lazy[node] = val;
return;
}
pushDownAssign(node, l, r);
int mid = l + (r-l)/2;
rangeAssign(2*node, l, mid, ql, qr, val);
rangeAssign(2*node+1, mid+1, r, ql, qr, val);
tree[node] = tree[2*node] + tree[2*node+1];
}lowbitEvery positive integer i has a lowest set bit — call it lowbit(i) = i & (-i).
For example: lowbit(6) = lowbit(110₂) = 010₂ = 2.
The Fenwick Tree exploits this:
i - lowbit(i) + 1 to i.[1..i]: sum up tree[i], tree[i - lowbit(i)], etc.Array (1-indexed): [_, 1, 2, 3, 4, 5, 6, 7, 8]
BIT responsibilities:
BIT[1] = arr[1] (1 element)
BIT[2] = arr[1] + arr[2] (2 elements: lowbit(2)=2)
BIT[3] = arr[3] (1 element)
BIT[4] = arr[1]+arr[2]+arr[3]+arr[4] (4 elements: lowbit(4)=4)
BIT[5] = arr[5] (1 element)
BIT[6] = arr[5] + arr[6] (2 elements)
BIT[7] = arr[7] (1 element)
BIT[8] = all 8 elements (8 elements: lowbit(8)=8)
Query prefix[1..6] = BIT[6] + BIT[4]
BIT[6] covers [5,6], then 6 - lowbit(6) = 4
BIT[4] covers [1,4], then 4 - lowbit(4) = 0 → done
Sum = (5+6) + (1+2+3+4) = 11 + 10 = 21 ✓
class BIT {
int n;
vector<long long> tree;
public:
BIT(int n) : n(n), tree(n+1, 0) {}
// Build from array: O(n) using repeated update
BIT(vector<int>& arr) : n(arr.size()), tree(arr.size()+1, 0) {
for (int i = 0; i < n; i++) update(i+1, arr[i]); // 1-indexed
}
// Add delta to position i (1-indexed)
void update(int i, long long delta) {
for (; i <= n; i += i & (-i)) // i & (-i) = lowbit(i)
tree[i] += delta;
}
// Prefix sum [1..i] (1-indexed)
long long query(int i) {
long long sum = 0;
for (; i > 0; i -= i & (-i))
sum += tree[i];
return sum;
}
// Range sum [l..r] (1-indexed, inclusive)
long long query(int l, int r) {
return query(r) - query(l-1);
}
// Point query (get value at position i)
long long pointQuery(int i) { return query(i) - query(i-1); }
};
// Update: O(log n), Query: O(log n), Space: O(n)
// Simpler and faster in practice than segment tree for this use caseUse a difference BIT: to add val to range [l, r], update D[l] += val and D[r+1] -= val. Point query becomes a prefix sum of D.
class BIT_RangeUpdate {
int n;
vector<long long> D; // Difference array stored in BIT
public:
BIT_RangeUpdate(int n) : n(n), D(n+2, 0) {}
void updatePoint(int i, long long delta) {
for (; i <= n; i += i & (-i)) D[i] += delta;
}
// Add val to all elements in [l, r]
void rangeAdd(int l, int r, long long val) {
updatePoint(l, val);
updatePoint(r+1, -val);
}
// Get current value at position i
long long pointQuery(int i) {
long long sum = 0;
for (; i > 0; i -= i & (-i)) sum += D[i];
return sum;
}
};
// rangeAdd: O(log n), pointQuery: O(log n)// Range add [l,r] + range sum query using two BITs B1 and B2
// Mathematical trick: prefix_sum(i) = B1.query(i)*i - B2.query(i)
class BIT_RangeUpdateRangeQuery {
int n;
BIT B1, B2;
void add(int l, int r, long long val) {
B1.update(l, val);
B1.update(r+1, -val);
B2.update(l, val * (l-1));
B2.update(r+1, -val * r);
}
long long prefixSum(int i) {
return B1.query(i) * i - B2.query(i);
}
public:
BIT_RangeUpdateRangeQuery(int n) : n(n), B1(n), B2(n) {}
void rangeAdd(int l, int r, long long val) { add(l, r, val); }
long long rangeSum(int l, int r) {
return prefixSum(r) - prefixSum(l-1);
}
};
// rangeAdd: O(log n), rangeSum: O(log n)class BIT2D {
int rows, cols;
vector<vector<long long>> tree;
public:
BIT2D(int r, int c) : rows(r), cols(c), tree(r+1, vector<long long>(c+1, 0)) {}
void update(int r, int c, long long delta) {
for (int i = r; i <= rows; i += i & (-i))
for (int j = c; j <= cols; j += j & (-j))
tree[i][j] += delta;
}
long long query(int r, int c) {
long long sum = 0;
for (int i = r; i > 0; i -= i & (-i))
for (int j = c; j > 0; j -= j & (-j))
sum += tree[i][j];
return sum;
}
// Rectangle sum [r1,c1] to [r2,c2] — inclusion-exclusion
long long query(int r1, int c1, int r2, int c2) {
return query(r2, c2) - query(r1-1, c2)
- query(r2, c1-1) + query(r1-1, c1-1);
}
};
// Update/Query: O(log(rows) × log(cols))What type of updates do you need?
│
├── Point updates only (update single element)?
│ └── Both work. BIT is simpler → USE BIT
│
├── Range updates (update a contiguous range)?
│ ├── Only need point queries after?
│ │ └── Use BIT with difference array (BIT_RangeUpdate)
│ └── Need range queries after?
│ └── Use Segment Tree with Lazy Propagation
│
What type of queries do you need?
│
├── Sum queries only?
│ └── BIT is simpler, faster → USE BIT
│
├── Min/Max queries?
│ └── BIT CANNOT do this → USE Segment Tree
│
├── Any other associative function (GCD, XOR, AND, OR)?
│ └── BIT CANNOT do this → USE Segment Tree
│
└── Complex queries (number of elements in range, kth element)?
└── USE Segment Tree (or BIT with binary lifting for kth)
| Fenwick Tree | Segment Tree | Seg Tree + Lazy | |
|---|---|---|---|
| Build | O(n log n) | O(n) | O(n) |
| Point update | O(log n) | O(log n) | O(log n) |
| Range update | O(log n) (diff BIT) | O(log n) | O(log n) |
| Point query | O(log n) | O(log n) | O(log n) |
| Range query | O(log n) | O(log n) | O(log n) |
| Supported ops | Sum only | Any associative | Any associative |
| Code complexity | Simple (~10 lines) | Moderate (~30 lines) | Complex (~50 lines) |
| Space | O(n) | O(4n) | O(4n) + O(4n) lazy |
| Constant factor | Small | Medium | Large |
Use Fenwick Tree when the problem involves point updates and prefix/range sums. It is faster, shorter, and less error-prone.
Use Segment Tree when you need range min/max, any non-additive function, or range updates with range queries.
When values are large (up to 10⁹) but sparse (n ≤ 10⁵), map them to indices 1..n before using a BIT or Segment Tree.
// Coordinate compression template
vector<int> compress(vector<int>& arr) {
vector<int> sorted = arr;
sort(sorted.begin(), sorted.end());
sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
// Map each value to its 1-indexed rank
vector<int> compressed(arr.size());
for (int i = 0; i < (int)arr.size(); i++) {
compressed[i] = lower_bound(sorted.begin(), sorted.end(), arr[i])
- sorted.begin() + 1; // 1-indexed
}
return compressed;
}
// Usage for "Count of Smaller Numbers After Self":
// Each number's compressed rank becomes its BIT index
// For each element (right to left): query how many smaller elements already seen,
// then insert this element's rank into the BIT.
int countSmaller(vector<int>& nums) {
int n = nums.size();
vector<int> sorted = nums;
sort(sorted.begin(), sorted.end());
sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
auto getRank = [&](int val) {
return lower_bound(sorted.begin(), sorted.end(), val) - sorted.begin() + 1;
};
BIT bit(sorted.size());
vector<int> result(n);
for (int i = n-1; i >= 0; i--) {
int rank = getRank(nums[i]);
result[i] = bit.query(rank - 1); // Count elements with rank < current
bit.update(rank, 1);
}
return result; // Wait, return vector — see Problem 2 below
}Support point updates and range sum queries on an array.
// Solution A: Fenwick Tree (preferred for pure sum queries)
class NumArray_BIT {
int n;
vector<long long> bit;
void update(int i, long long delta) {
for (i++; i <= n; i += i&-i) bit[i] += delta;
}
long long query(int i) {
long long s=0; for (i++; i>0; i-=i&-i) s+=bit[i]; return s;
}
public:
vector<int> arr;
NumArray_BIT(vector<int>& nums) : n(nums.size()), bit(n+1,0), arr(nums) {
for (int i=0; i<n; i++) update(i, nums[i]);
}
void update(int index, int val) {
update(index, val - arr[index]);
arr[index] = val;
}
int sumRange(int l, int r) { return query(r) - query(l-1); }
};
// Solution B: Segment Tree
class NumArray_SegTree {
int n;
vector<long long> tree;
void build(vector<int>& a, int node, int l, int r) {
if (l==r) { tree[node]=a[l]; return; }
int mid=l+(r-l)/2;
build(a,2*node,l,mid); build(a,2*node+1,mid+1,r);
tree[node]=tree[2*node]+tree[2*node+1];
}
void upd(int node, int l, int r, int pos, int val) {
if (l==r) { tree[node]=val; return; }
int mid=l+(r-l)/2;
if (pos<=mid) upd(2*node,l,mid,pos,val);
else upd(2*node+1,mid+1,r,pos,val);
tree[node]=tree[2*node]+tree[2*node+1];
}
long long qry(int node, int l, int r, int ql, int qr) {
if (qr<l||r<ql) return 0;
if (ql<=l&&r<=qr) return tree[node];
int mid=l+(r-l)/2;
return qry(2*node,l,mid,ql,qr)+qry(2*node+1,mid+1,r,ql,qr);
}
public:
int n2;
NumArray_SegTree(vector<int>& a) : n2(a.size()), tree(4*a.size()) {
build(a,1,0,n2-1);
}
void update(int i, int v) { upd(1,0,n2-1,i,v); }
int sumRange(int l, int r) { return qry(1,0,n2-1,l,r); }
};
// Both: Build O(n), Update O(log n), Query O(log n)For each element, count how many numbers to its right are smaller.
vector<int> countSmaller(vector<int>& nums) {
int n = nums.size();
// Coordinate compress
vector<int> sorted = nums;
sort(sorted.begin(), sorted.end());
sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
int m = sorted.size();
auto getRank = [&](int val) {
return lower_bound(sorted.begin(), sorted.end(), val) - sorted.begin() + 1;
};
vector<long long> bit(m+1, 0);
auto update = [&](int i) { for (; i<=m; i+=i&-i) bit[i]++; };
auto query = [&](int i) { long long s=0; for (; i>0; i-=i&-i) s+=bit[i]; return s; };
vector<int> result(n);
for (int i = n-1; i >= 0; i--) {
int rank = getRank(nums[i]);
result[i] = query(rank - 1); // Count elements with rank < current (already processed)
update(rank);
}
return result;
}
// Time: O(n log n), Space: O(n)n flights, k bookings. Each booking [first, last, seats] adds seats to flights [first, last]. Return the total seats booked for each flight.
// Difference array approach (simpler than BIT for this problem):
vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
vector<int> diff(n+2, 0);
for (auto& b : bookings) {
diff[b[0]] += b[2]; // Add at start
diff[b[1]+1] -= b[2]; // Remove after end
}
vector<int> result(n);
int curr = 0;
for (int i = 1; i <= n; i++) {
curr += diff[i];
result[i-1] = curr;
}
return result;
}
// Time: O(k + n), Space: O(n)
// BIT_RangeUpdate version (same complexity but shows BIT usage):
vector<int> corpFlightBookings_BIT(vector<vector<int>>& bookings, int n) {
vector<long long> D(n+2, 0);
auto upd = [&](int i, long long v) { for (; i<=n; i+=i&-i) D[i]+=v; };
auto qry = [&](int i) { long long s=0; for (; i>0; i-=i&-i) s+=D[i]; return s; };
for (auto& b : bookings) { upd(b[0], b[2]); upd(b[1]+1, -b[2]); }
vector<int> res(n);
for (int i=1; i<=n; i++) res[i-1] = qry(i);
return res;
}Count pairs (i, j) where i < j and nums[i] > 2 * nums[j].
// BIT with coordinate compression on all values (including 2*nums[j])
int reversePairs(vector<int>& nums) {
int n = nums.size();
vector<long long> all;
for (int x : nums) { all.push_back(x); all.push_back(2LL*x); }
sort(all.begin(), all.end());
all.erase(unique(all.begin(), all.end()), all.end());
int m = all.size();
auto getRank = [&](long long v) {
return lower_bound(all.begin(), all.end(), v) - all.begin() + 1;
};
vector<long long> bit(m+2, 0);
auto upd = [&](int i) { for (; i<=m; i+=i&-i) bit[i]++; };
auto qry = [&](int i) { long long s=0; for (; i>0; i-=i&-i) s+=bit[i]; return s; };
int count = 0;
for (int i = n-1; i >= 0; i--) {
// Count elements already seen (to the right of i) that are < nums[i]/2
// i.e., nums[j] < nums[i]/2 → 2*nums[j] < nums[i] → rank(nums[i]-1)
int r = getRank((long long)nums[i]) - 1;
count += qry(r);
upd(getRank((long long)2 * nums[i]));
}
return count;
}
// Time: O(n log n), Space: O(n)Return the maximum k-booking (maximum overlap at any moment) after each event added.
// Segment tree with lazy propagation on compressed coordinate space
class MyCalendarThree {
map<int, int> seg, lazy; // Implicit lazy segment tree using sorted map
int query(int l, int r, int lo, int hi, map<int,int>& s) { return 0; } // Placeholder
public:
// Simplified: use difference array + running maximum
map<int,int> diff;
int book(int start, int end) {
diff[start]++;
diff[end]--;
int curr = 0, maxK = 0;
for (auto& [t, d] : diff) {
curr += d;
maxK = max(maxK, curr);
}
return maxK;
}
};
// book: O(n) per call (scan sorted map), O(n) space
// For O(log n) per call: use Segment Tree with lazy on coordinate-compressed points
// Segment Tree with lazy (O(log n) per book call):
class MyCalendarThree_SegTree {
map<int, int> tree, lazy; // Sparse segment tree
void update(int l, int r, int lo, int hi, int node) {
if (r < lo || hi < l) return;
if (l <= lo && hi <= r) { tree[node]++; lazy[node]++; return; }
int mid = lo + (hi-lo)/2;
update(l, r, lo, mid, 2*node);
update(l, r, mid+1, hi, 2*node+1);
tree[node] = lazy[node] + max(tree[2*node], tree[2*node+1]);
}
int query(int lo, int hi, int node) { return tree[node]; }
public:
int book(int start, int end) {
update(start, end-1, 0, 1e9, 1);
return tree[1];
}
};
// book: O(log(MAX_VAL)), Space: O(n) sparse nodesSquares fall onto a number line. After each square falls, return the height of the tallest stack.
vector<int> fallingSquares(vector<vector<int>>& positions) {
// Coordinate compress all interval boundaries
vector<int> coords;
for (auto& p : positions) {
coords.push_back(p[0]);
coords.push_back(p[0] + p[1]);
}
sort(coords.begin(), coords.end());
coords.erase(unique(coords.begin(), coords.end()), coords.end());
int m = coords.size();
auto getIdx = [&](int x) {
return lower_bound(coords.begin(), coords.end(), x) - coords.begin();
};
// Lazy segment tree for range max with range assign
vector<int> tree(4*m, 0), lazy(4*m, 0);
function<void(int,int,int,int,int,int)> update = [&](int node, int l, int r, int ql, int qr, int val) {
if (qr<l||r<ql) return;
if (ql<=l&&r<=qr) { tree[node]=max(tree[node],val); lazy[node]=max(lazy[node],val); return; }
if (lazy[node]) { tree[2*node]=max(tree[2*node],lazy[node]); lazy[2*node]=max(lazy[2*node],lazy[node]);
tree[2*node+1]=max(tree[2*node+1],lazy[node]); lazy[2*node+1]=max(lazy[2*node+1],lazy[node]); lazy[node]=0; }
int mid=l+(r-l)/2;
update(2*node,l,mid,ql,qr,val); update(2*node+1,mid+1,r,ql,qr,val);
tree[node]=max(tree[2*node],tree[2*node+1]);
};
function<int(int,int,int,int,int)> query = [&](int node, int l, int r, int ql, int qr) -> int {
if (qr<l||r<ql) return 0;
if (ql<=l&&r<=qr) return tree[node];
if (lazy[node]) { tree[2*node]=max(tree[2*node],lazy[node]); lazy[2*node]=max(lazy[2*node],lazy[node]);
tree[2*node+1]=max(tree[2*node+1],lazy[node]); lazy[2*node+1]=max(lazy[2*node+1],lazy[node]); lazy[node]=0; }
int mid=l+(r-l)/2;
return max(query(2*node,l,mid,ql,qr), query(2*node+1,mid+1,r,ql,qr));
};
vector<int> result;
int maxH = 0;
for (auto& p : positions) {
int l = getIdx(p[0]), r = getIdx(p[0]+p[1])-1, side = p[1];
int curMax = query(1, 0, m-1, l, r);
int newH = curMax + side;
update(1, 0, m-1, l, r, newH);
maxH = max(maxH, newH);
result.push_back(maxH);
}
return result;
}
// Time: O(n log n), Space: O(n)Insert numbers one by one. Cost = min(count of smaller, count of larger). Return total cost.
int createSortedArray(vector<int>& instructions) {
const int MOD = 1e9+7;
int m = *max_element(instructions.begin(), instructions.end());
vector<long long> bit(m+1, 0);
auto upd = [&](int i) { for (; i<=m; i+=i&-i) bit[i]++; };
auto qry = [&](int i) { long long s=0; for (; i>0; i-=i&-i) s+=bit[i]; return s; };
long long cost = 0;
int cnt = 0;
for (int x : instructions) {
long long less_than = qry(x-1);
long long greater_than = cnt - qry(x);
cost = (cost + min(less_than, greater_than)) % MOD;
upd(x);
cnt++;
}
return cost;
}
// Time: O(n log M) where M = max value, Space: O(M)class NumMatrix {
int m, n;
vector<vector<long long>> bit;
void upd(int r, int c, long long delta) {
for (int i=r; i<=m; i+=i&-i)
for (int j=c; j<=n; j+=j&-j)
bit[i][j] += delta;
}
long long qry(int r, int c) {
long long s=0;
for (int i=r; i>0; i-=i&-i)
for (int j=c; j>0; j-=j&-j)
s += bit[i][j];
return s;
}
vector<vector<int>> mat;
public:
NumMatrix(vector<vector<int>>& matrix)
: m(matrix.size()), n(matrix[0].size()),
bit(m+1, vector<long long>(n+1, 0)), mat(matrix) {
for (int i=0; i<m; i++)
for (int j=0; j<n; j++)
upd(i+1, j+1, matrix[i][j]);
}
void update(int r, int c, int val) {
upd(r+1, c+1, val - mat[r][c]);
mat[r][c] = val;
}
int sumRegion(int r1, int c1, int r2, int c2) {
return qry(r2+1,c2+1) - qry(r1,c2+1) - qry(r2+1,c1) + qry(r1,c1);
}
};
// Update: O(log m × log n), Query: O(log m × log n)| # | Problem | Difficulty | Core Technique | Link |
|---|---|---|---|---|
| 1 | Range Sum Query - Mutable | Medium | Fenwick Tree / Segment Tree | LC 307 |
| 2 | Corporate Flight Bookings | Medium | Difference array / BIT range update | LC 1109 |
| 3 | Count of Smaller Numbers After Self | Hard | BIT + coordinate compression | LC 315 |
| 4 | Reverse Pairs | Hard | BIT + coordinate compression | LC 493 |
| 5 | Create Sorted Array through Instructions | Hard | BIT on value range | LC 1649 |
| 6 | My Calendar III | Hard | Segment tree (sparse/lazy) | LC 732 |
| 7 | Falling Squares | Hard | Segment tree + coord compression | LC 699 |
| 8 | Range Sum Query 2D - Mutable | Hard | 2D Fenwick Tree | LC 308 |
Suggested order: #1 (Range Sum Mutable) — implement both BIT and Segment Tree solutions. #2 (Flight Bookings) — understand range-update via difference array before using BIT. #3 (Count Smaller) — the canonical BIT + coordinate compression problem. #4 and #5 follow the same pattern. #6, #7, #8 are hard real-world applications — tackle after the BIT problems are solid.