Week 19: Advanced Data Structures — CodeVerse Creatives

1. Segment Trees: Range Queries & Point Updates

A segment tree answers range queries (sum, min, max, gcd) over an array that also supports point updates, both in O(log n). It's a binary tree stored in an array where each node covers a contiguous range, and a parent's value is the merge of its two children's values.

segment_tree.cpp

#include <vector>
using namespace std;

class SegmentTree {
public:
    SegmentTree(const vector<int>& nums) {
        n = nums.size();
        tree.assign(4 * n, 0);
        if (n > 0) build(nums, 1, 0, n - 1);
    }

    // Sum of nums[l..r] inclusive -- O(log n)
    int query(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }

    // Set nums[idx] = val -- O(log n)
    void update(int idx, int val) {
        update(1, 0, n - 1, idx, val);
    }

private:
    vector<int> tree;
    int n;

    void build(const vector<int>& nums, int node, int lo, int hi) {
        if (lo == hi) { tree[node] = nums[lo]; return; }
        int mid = lo + (hi - lo) / 2;
        build(nums, 2 * node, lo, mid);
        build(nums, 2 * node + 1, mid + 1, hi);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    int query(int node, int lo, int hi, int l, int r) {
        if (r < lo || hi < l) return 0;                  // no overlap
        if (l <= lo && hi <= r) return tree[node];        // total overlap
        int mid = lo + (hi - lo) / 2;
        return query(2 * node, lo, mid, l, r) + query(2 * node + 1, mid + 1, hi, l, r);
    }

    void update(int node, int lo, int hi, int idx, int val) {
        if (lo == hi) { tree[node] = val; return; }
        int mid = lo + (hi - lo) / 2;
        if (idx <= mid) update(2 * node, lo, mid, idx, val);
        else update(2 * node + 1, mid + 1, hi, idx, val);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
};

Change the merge, get a different query

Swap tree[node] = tree[2*node] + tree[2*node+1] for min(...) or max(...) (and change the "no overlap" sentinel from 0 to INT_MAX or INT_MIN) and the exact same recursive structure answers range-min or range-max queries instead of range-sum.

2. Lazy Propagation for Range Updates

The segment tree above only supports point updates — setting one index. Adding a value to every element in a range naively would mean touching O(n) nodes per update, destroying the tree's O(log n) guarantee. Lazy propagation fixes this: when a range update fully covers a node's range, stamp a pending change on that node and stop — don't recurse into its children yet. That pending change only gets pushed down to the children the next time something actually needs to look inside them.

segment_tree_lazy.cpp

#include <vector>
using namespace std;

class LazySegmentTree {
public:
    LazySegmentTree(const vector<long long>& nums) {
        n = nums.size();
        tree.assign(4 * n, 0);
        lazy.assign(4 * n, 0);
        if (n > 0) build(nums, 1, 0, n - 1);
    }

    // Add `delta` to every element in nums[l..r] -- O(log n)
    void updateRange(int l, int r, long long delta) {
        updateRange(1, 0, n - 1, l, r, delta);
    }

    // Sum of nums[l..r] -- O(log n)
    long long query(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }

private:
    vector<long long> tree, lazy;
    int n;

    void build(const vector<long long>& nums, int node, int lo, int hi) {
        if (lo == hi) { tree[node] = nums[lo]; return; }
        int mid = lo + (hi - lo) / 2;
        build(nums, 2 * node, lo, mid);
        build(nums, 2 * node + 1, mid + 1, hi);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    void pushDown(int node, int lo, int hi) {
        if (lazy[node] == 0) return;
        int mid = lo + (hi - lo) / 2;
        int leftLen = mid - lo + 1, rightLen = hi - mid;

        // Apply this node's pending delta to both children before touching them
        tree[2 * node] += lazy[node] * leftLen;
        lazy[2 * node] += lazy[node];
        tree[2 * node + 1] += lazy[node] * rightLen;
        lazy[2 * node + 1] += lazy[node];

        lazy[node] = 0;   // pending change has been handed off -- clear it
    }

    void updateRange(int node, int lo, int hi, int l, int r, long long delta) {
        if (r < lo || hi < l) return;                     // no overlap
        if (l <= lo && hi <= r) {                          // total overlap
            tree[node] += delta * (hi - lo + 1);
            lazy[node] += delta;                            // defer pushing to children
            return;
        }
        pushDown(node, lo, hi);                             // partial overlap: must recurse
        int mid = lo + (hi - lo) / 2;
        updateRange(2 * node, lo, mid, l, r, delta);
        updateRange(2 * node + 1, mid + 1, hi, l, r, delta);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    long long query(int node, int lo, int hi, int l, int r) {
        if (r < lo || hi < l) return 0;
        if (l <= lo && hi <= r) return tree[node];
        pushDown(node, lo, hi);                             // must resolve pending changes first
        int mid = lo + (hi - lo) / 2;
        return query(2 * node, lo, mid, l, r) + query(2 * node + 1, mid + 1, hi, l, r);
    }
};

lazy[node] means "every element under this node still owes a pending +delta that hasn't been applied to the children yet, only reflected in this node's own aggregate." Both updateRange and query call pushDown before recursing into a node's children — that's the rule that guarantees a child is never read while it still has an un-applied pending change sitting above it. Because each level of the tree does O(1) work per visited node and the recursion still only visits O(log n) nodes per call, both operations stay O(log n) despite touching a whole range at once.

"Lazy" means deferred, not skipped

Every pending change eventually does get applied — lazy propagation doesn't do less total work than eagerly updating every element, it just defers that work until a query or a later update actually needs to look inside the subtree, and a range that's never queried after being updated never pays the cost of expanding down to individual elements at all.

3. Fenwick Trees (Binary Indexed Trees)

A Fenwick tree (BIT) answers prefix-sum queries and point updates in O(log n), with far less code than a segment tree — at the cost of only supporting operations that are invertible, like sum or XOR, not min or max.

fenwick_tree.cpp

#include <vector>
using namespace std;

class FenwickTree {
public:
    FenwickTree(int n) : tree(n + 1, 0) {}

    // Add delta to index i (1-indexed) -- O(log n)
    void update(int i, int delta) {
        for (; i < (int)tree.size(); i += i & (-i)) {
            tree[i] += delta;
        }
    }

    // Prefix sum of [1..i] -- O(log n)
    int prefixSum(int i) {
        int sum = 0;
        for (; i > 0; i -= i & (-i)) {
            sum += tree[i];
        }
        return sum;
    }

    // Range sum [l..r], both 1-indexed and inclusive -- O(log n)
    int rangeSum(int l, int r) {
        return prefixSum(r) - prefixSum(l - 1);
    }

private:
    vector<int> tree;
};

i & (-i) isolates the lowest set bit of i, which is the size of the range that index is responsible for. update walks upward adding that range size to move to the next node that needs updating; prefixSum walks downward subtracting it to accumulate the answer — the same bit trick powers both directions.

Default to Fenwick when sum is all you need

Whenever a problem needs point updates plus range-sum (or prefix-sum) queries, a Fenwick tree is usually the faster thing to code correctly under time pressure — reach for a segment tree only when the operation isn't invertible (min, max, gcd) or you need range updates too, via lazy propagation.

4. Sparse Tables: O(1) Range-Minimum Queries on a Static Array

When the array never changes after being built, a sparse table beats every structure above: O(n log n) preprocessing buys true O(1) queries, with no log n factor at all. The idea: precompute the minimum of every range whose length is a power of two, then answer any query by covering it with two overlapping power-of-two ranges — overlap is fine for an idempotent operation like min or max, where combining the same element twice doesn't change the answer.

sparse_table.cpp

#include <vector>
#include <cmath>
using namespace std;

class SparseTable {
public:
    // O(n log n) preprocessing
    SparseTable(const vector<int>& nums) {
        int n = nums.size();
        int maxLog = log2(n) + 1;
        table.assign(maxLog, vector<int>(n));
        table[0] = nums;   // ranges of length 2^0 = 1 are just the elements themselves

        for (int k = 1; k < maxLog; k++) {
            int len = 1 << k;
            for (int i = 0; i + len <= n; i++) {
                // Range [i, i+len) = combine [i, i+len/2) and [i+len/2, i+len)
                table[k][i] = min(table[k - 1][i], table[k - 1][i + len / 2]);
            }
        }
    }

    // Minimum of nums[l..r] inclusive -- O(1)
    int query(int l, int r) {
        int len = r - l + 1;
        int k = log2(len);
        // Two overlapping ranges of length 2^k together cover [l, r] -- overlap is
        // harmless because min() is idempotent
        return min(table[k][l], table[k][r - (1 << k) + 1]);
    }

private:
    vector<vector<int>> table;
};

table[k][i] holds the minimum of the 2ᵡ-length range starting at i, built from two half-length ranges already computed at level k - 1 — the same "build longer ranges from shorter, already-solved ones" discipline as Week 14's interval DP, just restricted to power-of-two lengths. Because any range [l, r] can be covered by two possibly-overlapping power-of-two ranges (one anchored at l, one anchored at r), every query is a single lookup and one min — no recursion, no log-factor traversal.

The overlap trick only works for idempotent operations

Range-sum can't use this trick — summing the same overlapping elements twice would double-count them, which is exactly why sparse tables are the go-to for range-min/max/gcd/AND/OR (all idempotent) but never for range-sum, where a Fenwick tree or segment tree is required instead.

5. Hands-on Exercise

Hands-on

Build a complete range-query toolkit

Implement all four structures — including Week 2's static prefix sum as a baseline — and confirm they agree on the queries each one supports.

Requirements:

Implement SegmentTree and FenwickTree, and confirm both agree with a static buildPrefixSum/rangeSumStatic pair on data that never changes.
Implement LazySegmentTree and test a sequence of overlapping range updates followed by range-sum queries; confirm the results match a naive O(n)-per-update array simulation.
Implement SparseTable for range-minimum and confirm it agrees with SegmentTree adapted for range-min (swap the merge to min, as in Section 1's callout) on the same static array.
Write a one-line comment above each structure stating when to reach for it and its Big-O for build/update/query, covering: no updates, point updates only, range updates, and idempotent-operation-only queries.
As a stretch goal, adapt LazySegmentTree to support range assignment (set every element in a range to a fixed value) instead of range addition, and explain in a comment why the pushDown logic changes from adding the lazy value to overwriting with it.

Hint

For requirement 5: with range assignment, a pending "set to X" completely overwrites whatever a child's own pending change was, rather than combining with it — so pushDown should overwrite the children's lazy values instead of adding to them, and you'll need a sentinel (like a boolean "has pending assignment") to distinguish "no pending change" from "pending change of value 0."

6. Knowledge Check

Four quick questions. Expand each to check your answer.

In a lazy segment tree, what does `lazy[node] != 0` mean, and why must both `updateRange` and `query` call `pushDown` before recursing into a node's children?

lazy[node] != 0 means every element under this node has a pending change that's reflected in this node's own aggregate value but hasn't yet been applied to the children individually. If either operation read or modified a child without first pushing that pending change down, the child's value would be stale — missing an update that logically already happened — so pushing down before descending is what keeps every node's value consistent with its actual pending history.

Why can a Fenwick tree support range-sum but not range-minimum, even though both are "range query" operations?

Fenwick's rangeSum(l, r) works by subtracting prefixSum(l-1) from prefixSum(r) — that only produces a correct answer because addition is invertible (subtraction undoes it). Minimum has no inverse operation: knowing the minimum of [1, r] and the minimum of [1, l-1] tells you nothing about the minimum of just [l, r], since the overall minimum could have come from either sub-range or been excluded by the subtraction entirely.

Why does a sparse table's O(1) range-minimum query correctly handle the two power-of-two ranges it uses overlapping each other?

Minimum is idempotent — taking the minimum of a value together with itself just returns that same value, so an element counted in both overlapping ranges doesn't distort the result. This wouldn't hold for sum, where counting an element twice would incorrectly inflate the total, which is exactly why the overlap trick is restricted to idempotent operations like min, max, gcd, AND, and OR.

Given a static array (no updates ever) and a need for range-minimum queries, why would a sparse table beat both a segment tree and a Fenwick tree?

A Fenwick tree can't do range-minimum at all (see Q2), so it's ruled out regardless. A segment tree adapted for range-min still costs O(log n) per query, because it always pays for the possibility of updates even when none ever happen. A sparse table spends more one-time preprocessing (O(n log n)) specifically to eliminate that per-query log factor entirely, which only pays off because the array never changes — the moment updates are needed, the sparse table's O(1) query is no longer maintainable and a segment tree becomes the right choice again.

Week 19: Advanced Data Structures — Segment Trees, Fenwick Trees & Sparse Tables

By the end of this week, you'll be able to

1. Segment Trees: Range Queries & Point Updates

2. Lazy Propagation for Range Updates

3. Fenwick Trees (Binary Indexed Trees)

4. Sparse Tables: O(1) Range-Minimum Queries on a Static Array

5. Hands-on Exercise

Build a complete range-query toolkit

6. Knowledge Check

In a lazy segment tree, what does `lazy[node] != 0` mean, and why must both `updateRange` and `query` call `pushDown` before recursing into a node's children?

Why can a Fenwick tree support range-sum but not range-minimum, even though both are "range query" operations?

Why does a sparse table's O(1) range-minimum query correctly handle the two power-of-two ranges it uses overlapping each other?

Given a static array (no updates ever) and a need for range-minimum queries, why would a sparse table beat both a segment tree and a Fenwick tree?

Week 19: Advanced Data Structures — Segment Trees, Fenwick Trees & Sparse Tables

By the end of this week, you'll be able to

1. Segment Trees: Range Queries & Point Updates

2. Lazy Propagation for Range Updates

3. Fenwick Trees (Binary Indexed Trees)

4. Sparse Tables: O(1) Range-Minimum Queries on a Static Array

5. Hands-on Exercise

Build a complete range-query toolkit

6. Knowledge Check

In a lazy segment tree, what does lazy[node] != 0 mean, and why must both updateRange and query call pushDown before recursing into a node's children?

Why can a Fenwick tree support range-sum but not range-minimum, even though both are "range query" operations?

Why does a sparse table's O(1) range-minimum query correctly handle the two power-of-two ranges it uses overlapping each other?

Given a static array (no updates ever) and a need for range-minimum queries, why would a sparse table beat both a segment tree and a Fenwick tree?

In a lazy segment tree, what does `lazy[node] != 0` mean, and why must both `updateRange` and `query` call `pushDown` before recursing into a node's children?