Range Update Point Query

Standard BIT: point update, prefix query.

What if you need: range update, point query?

Use a difference array with BIT! Let diff[i] = arr[i] - arr[i-1]. Then:

• arr[i] = prefix(diff, i). Point query becomes prefix sum
• To add $\delta$ to range $[l, r]$: add $\delta$ to diff[l], add $-\delta$ to diff[r+1]

def rangeAdd(l, r, delta):
    update(l, delta)       # diff[l] += delta
    update(r + 1, -delta)  # diff[r+1] -= delta

def pointQuery(i):
    return prefix(i)  # sum of differences = arr[i]

You get $O(\log n)$ range update and $O(\log n)$ point query.