Chapter 101

Home

Refactoring: Range Updates with BIT

A single BIT supports point updates + prefix queries. Two BITs together support range updates + range queries — add val to [l, r], query sum of [l, r]. All O(log N), no lazy propagation needed.

Before: Point-by-Point Range Update

C++ — O(N log N) range update

for (int i = l; i <= r; i++) bit.add(i, val);  // O(N log N)

After: Range Update with Two BITs

C++ — range update + range query with two BITs

struct RangeBIT {
    BIT B1, B2;  // two Fenwick trees

    void range_add(int l, int r, long long val) {
        B1.add(l, val);
        B1.add(r + 1, -val);
        B2.add(l, val * (l - 1));
        B2.add(r + 1, -val * r);
    }

    long long prefix_sum(int idx) {
        return B1.sum(idx) * idx - B2.sum(idx);
    }

    long long range_sum(int l, int r) {
        return prefix_sum(r) - prefix_sum(l - 1);
    }
};

// Both operations O(log N).
// Derivation: sum(1..x) = x × ΣB1[i] − Σ(B1[i] × (i-1))

Key Takeaways