You are not logged in. Please login at www.codechef.com to post your questions!

×

BIT - Range update and point query

1
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.

asked 23 Mar '16, 16:05

prrateekk's gravatar image

4★prrateekk
534115
accept rate: 12%

edited 23 Mar '16, 16:07


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(p): 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.

link

answered 23 Mar '16, 17:45

ceilks's gravatar image

7★ceilks
1.8k8
accept rate: 36%

1

That was really clever! Thanks for sharing @ceilks

(25 Mar '16, 16:48) prrateekk4★

I have spent many days to understand range update, wrote simple explanation with example here: https://github.com/manoharreddyporeddy/AdvancedDataStructuresAndAlgorithms/blob/master/BIT_fenwick_tree_explanation.md

link

answered 05 Nov, 07:39

pgmreddy's gravatar image

0★pgmreddy
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×522
×303
×146
×52
×36

question asked: 23 Mar '16, 16:05

question was seen: 1,929 times

last updated: 05 Nov, 07:39