BIT - Range update and point query

general
, , , ,
1

I read this article - KartikKukreja’s blog. I clearly understood the point update and range query,but couldn’t understand the range updates.
For updating the range a to b , the following code is used -

# Add v to A[p]

update(p, v):

for (; p <= N; p += p&(-p))

ft[p] += v


# Add v to A[a…b] 

update(a, b, v):

update(a, v)

update(b + 1, -v)


# Return A[b]	 

query(b):

sum = 0

for(; b > 0; b -= b&(-b))

sum += ft[b]

return sum

Since the update(a,v) was earlier used for point update, How is it used for range update in this code.Also,the query(b) function earlier returned the result for 1 to b. How in this code is it returning the result for just b(and not 1 to b).

I did a lot of search, but couldn’t find any satisfactory answer.Please help.

1 Like
2

Let’s forget about the implementation for a moment. The basic BIT provides you with two basic operations on an abstract array:

  1. update(p,v): add v to the pth element
  2. query§: get the cumulative sum from 1 to p

Implementing point updates and range queries with these basic operations is easy. But how to get to range updates / point queries?

Instead of working on the array you’re actually interested in, work on the array containing the differences from one item to the next. Then the original array is just the cumulative sum, so you can actually use operation 2 to retrieve values.

For the update operation: How do the differences change when you add a constant value v for each element in a range? Simple: the first element gets incremented by v, the element after the end of the range gets decremented by v - that’s just what the new function update(a,b,v) does.

4 Likes
3

That was really clever! Thanks for sharing @ceilks

1 Like
4

I have spent many days to understand range update, wrote simple explanation with example here: