Range Update Range Query

What if you need both range updates AND range queries?

Use two BITs. After adding $\delta$ to range $[l, r]$, the prefix sum at position $i$ increases by:

• $0$ if $i < l$
• $\delta \cdot (i - l + 1)$ if $l \leq i \leq r$
• $\delta \cdot (r - l + 1)$ if $i > r$

This can be decomposed into: $\text{prefix}(i) = B_1(i) \cdot i - B_0(i)$

where $B_1$ and $B_0$ are two BITs updated together.

def rangeAdd(l, r, delta):
    add(B1, l, delta)
    add(B1, r + 1, -delta)
    add(B0, l, delta * (l - 1))
    add(B0, r + 1, -delta * r)

def prefixSum(i):
    return query(B1, i) * i - query(B0, i)

This achieves $O(\log n)$ for both range update and range query.