×

# BIT - Range update and point query

 1 2 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 534●1●15 accept rate: 12%

 4 Let's forget about the implementation for a moment. The basic BIT provides you with two basic operations on an abstract array: update(p,v): add v to the pth element 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. answered 23 Mar '16, 17:45 7★ceilks 1.8k●9 accept rate: 36% 1 That was really clever! Thanks for sharing @ceilks (25 Mar '16, 16:48)
 0 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 answered 05 Nov '17, 07:39 0★pgmreddy 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×666
×367
×146
×63
×53

question asked: 23 Mar '16, 16:05

question was seen: 2,421 times

last updated: 05 Nov '17, 07:39