Range Operations

March 2026 · 22 min read

So far we've covered the classic Fenwick tree: point updates + prefix queries. But what if you need to update an entire range at once? Or query a range after range updates? This post shows how to handle both, using clever transformations on top of the same BIT structure.

Operation Matrix

Range Update + Point Query

The Idea: Difference Arrays

A difference array D is defined as D[i] = arr[i] - arr[i-1] (with D[1] = arr[1]). The key property: arr[i] = D[1] + D[2] + ... + D[i], that is, the original array value at position i is the prefix sum of the difference array.

Now, adding val to every element in arr[l..r] only changes two entries in D:

D[l]     += val   // the range starts here
D[r + 1] -= val   // the range ends here (undo the effect)

If we build a BIT over the difference array D, then:

• Range update arr[l..r] += val: two point updates on the BIT: update(l, +val), update(r+1, -val)
• Point query arr[i]: prefix query on the BIT: query(i) = D[1] + ... + D[i] = arr[i]

class RangeUpdatePointQuery {
    FenwickTree bit;  // BIT over the difference array
public:
    RangeUpdatePointQuery(int n) : bit(n) {}

    // Add val to arr[l..r]
    void range_update(int l, int r, int val) {
        bit.update(l, val);
        bit.update(r + 1, -val);
    }

    // Get current value of arr[i]
    int point_query(int i) {
        return bit.query(i);  // prefix sum of difference array
    }
};

Range Update + Range Query

The Challenge

With the difference array approach, we can get arr[i] in O(log n). But what about prefix_sum(i) = arr[1] + arr[2] + ... + arr[i]? Each arr[j] is itself a prefix sum of D, so:

prefix_sum(i) = Σ(j=1 to i) arr[j]
              = Σ(j=1 to i) Σ(k=1 to j) D[k]

Expanding this double sum:

prefix_sum(i) = D[1]·i + D[2]·(i-1) + D[3]·(i-2) + ... + D[i]·1
              = Σ(k=1 to i) D[k] · (i - k + 1)
              = (i + 1) · Σ(k=1 to i) D[k]  -  Σ(k=1 to i) D[k] · k

We need two prefix sums: Σ D[k] and Σ D[k]·k. Each can be maintained by its own BIT!

class RangeUpdateRangeQuery {
    FenwickTree bit1;  // stores D[k]
    FenwickTree bit2;  // stores D[k] * k
    int n;
public:
    RangeUpdateRangeQuery(int n) : n(n), bit1(n), bit2(n) {}

    // Add val to arr[l..r]
    void range_update(int l, int r, int val) {
        bit1.update(l, val);
        bit1.update(r + 1, -val);
        bit2.update(l, val * l);
        bit2.update(r + 1, -val * (r + 1));
    }

    // Prefix sum: arr[1] + ... + arr[i]
    int prefix_sum(int i) {
        return (i + 1) * bit1.query(i) - bit2.query(i);
    }

    // Range sum: arr[l] + ... + arr[r]
    int range_sum(int l, int r) {
        return prefix_sum(r) - prefix_sum(l - 1);
    }
};

Why Two BITs?

The formula prefix_sum(i) = (i+1)·Σ D[k] - Σ(D[k]·k) separates the dependency on i from the data. Both Σ D[k] and Σ(D[k]·k) are prefix sums that can be maintained by BITs. At query time, we just combine them with the formula.

During range_update(l, r, val), we update both BITs:

• bit1: add val at l, subtract at r+1 (same as before)
• bit2: add val·l at l, subtract val·(r+1) at r+1 (to maintain Σ D[k]·k)

The Math Behind Two BITs

Let's verify the formula step by step. Define D as the difference array, so arr[i] = Σ(k=1..i) D[k].

prefix_sum(i) = Σ(j=1..i) arr[j]
              = Σ(j=1..i) Σ(k=1..j) D[k]

Count how many times D[k] appears: it appears in arr[k], arr[k+1], ..., arr[i]
So D[k] appears (i - k + 1) times.

prefix_sum(i) = Σ(k=1..i) D[k] · (i - k + 1)
              = Σ(k=1..i) D[k] · (i + 1) - Σ(k=1..i) D[k] · k
              = (i + 1) · Σ(k=1..i) D[k]   -  Σ(k=1..i) k · D[k]
              = (i + 1) · prefix_bit1(i)    -  prefix_bit2(i)

Both prefix_bit1(i) and prefix_bit2(i) are standard BIT prefix queries. After a range update arr[l..r] += val:

• D[l] += val, D[r+1] -= val
• In bit1: update(l, +val), update(r+1, -val)
• In bit2: update(l, +val·l), update(r+1, -val·(r+1))

Choosing the Right Variant

Even the "two BIT" variant is simpler and uses less memory than a segment tree with lazy propagation. When the operations are just additions, Fenwick trees are almost always the better choice.

Summary

• Difference arrays turn range updates into two point updates. Building a BIT over the difference array gives O(log n) range update + O(log n) point query.
• For range update + range query, maintain two BITs: one for D[k] and one for k·D[k]. Combine at query time with prefix(i) = (i+1)·bit1.query(i) - bit2.query(i).
• All three variants use O(n) space total and O(log n) per operation.

Practice Problems

These target the range-update variants: difference-array updates, the two-BIT range-update + range-query trick, and related offline range work.