Chapter 20 of 30
Coordinate Compression, Fenwick Tree & Segment Tree
Master coordinate compression, Fenwick trees, segment trees, and sparse tables for efficient range queries and updates.
Coordinate CompressionFenwick Tree (Binary Indexed Tree)Segment TreeSparse Table (D1 — Recognition)
Share:
Coordinate Compression, Fenwick Tree & Segment Tree
When you need to query or update ranges efficiently, these data structures are essential. Fenwick trees are simpler and faster for prefix queries; segment trees handle arbitrary range queries.
Coordinate Compression
Map large values to a compact range [0, k-1]:
hljs cpp
vector<int> v = {1000000, 50, 1000000, 42, 50};
vector<int> sorted_v = v;
sort(sorted_v.begin(), sorted_v.end());
sorted_v.erase(unique(sorted_v.begin(), sorted_v.end()), sorted_v.end());
// Map each value to its compressed index
for (int &x : v) {
x = lower_bound(sorted_v.begin(), sorted_v.end(), x) - sorted_v.begin();
}
// v = {2, 0, 2, 1, 0}
// sorted_v = {42, 50, 1000000}
Use when: values are large but the number of distinct values is small.
Fenwick Tree (Binary Indexed Tree)
Supports prefix sum queries and point updates in O(log n):
hljs cpp
struct Fenwick {
int n;
vector<long long> bit;
Fenwick(int n) : n(n), bit(n + 1, 0) {}
void update(int i, long long delta) {
for (i++; i <= n; i += i & (-i))
bit[i] += delta;
}
long long query(int i) { // prefix sum [0, i]
long long sum = 0;
for (i++; i > 0; i -= i & (-i))
sum += bit[i];
return sum;
}
long long query(int l, int r) { // range sum [l, r]
return query(r) - query(l - 1);
}
};
Usage
hljs cpp
Fenwick fw(n);
// Point update: add v to index i
fw.update(i, v);
// Range sum query [l, r]
long long sum = fw.query(l, r);
Inversion Count
hljs cpp
Fenwick fw(MAX);
long long inversions = 0;
for (int i = n - 1; i >= 0; i--) {
inversions += fw.query(0, a[i] - 1);
fw.update(a[i], 1);
}
Segment Tree
Supports arbitrary range queries and range updates in O(log n):
hljs cpp
struct SegTree {
int n;
vector<long long> tree;
SegTree(int n) : n(n), tree(4 * n, 0) {}
void build(vector<int> &a, int node, int start, int end) {
if (start == end) {
tree[node] = a[start];
} else {
int mid = (start + end) / 2;
build(a, 2 * node, start, mid);
build(a, 2 * node + 1, mid + 1, end);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
}
void update(int node, int start, int end, int idx, long long val) {
if (start == end) {
tree[node] = val;
} else {
int mid = (start + end) / 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];
}
}
long long 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);
}
};
Usage
hljs cpp
SegTree st(n);
st.build(a, 1, 0, n - 1);
st.update(1, 0, n - 1, idx, newValue);
long long sum = st.query(1, 0, n - 1, l, r);
Lazy Propagation (Range Updates)
For adding a value to all elements in a range:
hljs cpp
struct SegTreeLazy {
int n;
vector<long long> tree, lazy;
void pushDown(int node, int start, int end) {
if (lazy[node] != 0) {
int mid = (start + end) / 2;
tree[2 * node] += lazy[node] * (mid - start + 1);
tree[2 * node + 1] += lazy[node] * (end - mid);
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, long long val) {
pushDown(node, start, end);
if (r < start || end < l) return;
if (l <= start && end <= r) {
tree[node] += val * (end - start + 1);
lazy[node] += 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);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
};
Sparse Table (D1 — Recognition)
O(1) range minimum/maximum queries after O(n log n) preprocessing:
hljs cpp
vector<vector<int>> sparseTable(vector<int> &a) {
int n = a.size();
int k = __lg(n) + 1;
vector<vector<int>> st(k, vector<int>(n));
for (int i = 0; i < n; i++) st[0][i] = a[i];
for (int j = 1; j < k; j++) {
for (int i = 0; i + (1 << j) <= n; i++) {
st[j][i] = min(st[j-1][i], st[j-1][i + (1 << (j-1))]);
}
}
return st;
}
// Query: minimum in [l, r]
int query(vector<vector<int>> &st, int l, int r) {
int k = __lg(r - l + 1);
return min(st[k][l], st[k][r - (1 << k) + 1]);
}
Summary
- Fenwick tree: simpler, faster, O(log n) for prefix sums + point updates
- Segment tree: more flexible, O(log n) for any range query + range updates (with lazy)
- Sparse table: O(1) range min/max queries, but no updates
- Coordinate compression: map large values to compact range
- Use Fenwick for prefix sums; segment tree for arbitrary ranges; sparse table for static min/max
Prefer reading offline? Download the full book as a PDF.
Download Free Book