What if you need both range updates AND range queries?
Use two BITs. After adding to range , the prefix sum at position increases by:
- if
- if
- if
This can be decomposed into:
where and 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 for both range update and range query.