I described implementation of BIT/Fenwick tree in an earlier post as a way of maintaining cumulative frequency table, which allows operations like updating any single element and querying sum of elements in a range [a…b] in logarithmic time. I recently found out that this is only one of the ways of using a BIT. A BIT can in fact be operated in one of three modes:
1. Point Updates and Range Queries
Given an array A of N numbers, we need to support adding a value v to any element A[p] and querying the sum of numbers A[a] + A[a+1] + … + A[b], both operations in O(log N). Let ft[N+1] denotes the underlying fenwick tree.
| # Add v to A[p] | |
| update(p, v): | |
| for (; p <= N; p += p&(-p)) | |
| ft[p] += v | |
| # Return sum A[1...b] | |
| query(b): | |
| sum = 0 | |
| for(; b > 0; b -= b&(-b)) | |
| sum += ft[b] | |
| return sum | |
| # Return sum A[a...b] | |
| query(a, b): | |
| return query(b) - query(a-1) |
Take a look at C++ implementation.
2. Range Updates and Point queries
Given an array A of N numbers, we need to support adding a value v to each element A[a…b] and querying the value of A[p], both operations in O(log N). Let ft[N+1] denote the underlying fenwick tree.
| # A[] is the original array | |
| # ft[] is the fenwick tree maintaining the diffs initialized with 0 | |
| # 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 + A[b] |
Explanation: update(p, v) will affect all p’ >= p. To limit the effect to a given range [a…b], we subtract -v from all p’ > b by performing the operation update(b+1, -v).
See problem UPDATEIT which uses this idea.
Take a look at C++ implementation.
3. Range Updates and Range Queries
Given an array A of N numbers, we need to support adding a value v to each element A[a…b] and querying the sum of numbers A[a…b], both operations in O(log N). This can be done by using two BITs B1[N+1], B2[N+1].
| update(ft, p, v): | |
| for (; p <= N; p += p&(-p)) | |
| ft[p] += v | |
| # Add v to A[a...b] | |
| update(a, b, v): | |
| update(B1, a, v) | |
| update(B1, b + 1, -v) | |
| update(B2, a, v * (a-1)) | |
| update(B2, b + 1, -v * b) | |
| query(ft, b): | |
| sum = 0 | |
| for(; b > 0; b -= b&(-b)) | |
| sum += ft[b] | |
| return sum | |
| # Return sum A[1...b] | |
| query(b): | |
| return query(B1, b) * b - query(B2, b) | |
| # Return sum A[a...b] | |
| query(a, b): | |
| return query(b) - query(a-1) |
Explanation:
BIT B1 is used like in the earlier case with range updates/point queries such that query(B1, p) gives A[p].
Consider a range update query: Add v to [a…b]. Let all elements initially be 0. Now, Sum(1…p) for different p is as follows:
- 1 <= p < a : 0
- a <= p <= b : v * (p – (a – 1))
- b < p <= N : v * (b – (a – 1))
Thus, for a given index p, we can find Sum(1…p) by subtracting a value X from p * Sum(p,p) (Sum(p,p) is the actual value stored at index p) such that
- 1 <= p < a : Sum(1..p) = 0, X = 0
- a <= p <= b : Sum(1…p) = (v * p) – (v * (a-1)), X = v * (a-1)
- b < p <= N: Sum(1…p) = (v * b) – (v * (a-1)), X = -(v * b) + (v * (a-1))
To maintain this extra factor X, we use another BIT B2 such that
- Add v to [a…b] -> Update(B2, a, v * (a-1)) and Update(B2, b+1, -v * b)
- Query(B2, p) gives the value X that must be subtracted from A[p] * p
See problem HORRIBLE which uses this idea.
Take a look at C++ implementation.
References:
Everything Under The Sun 
what if i’m updating with different values not with v i.e. for every element i update with it’s unique value ?
BITs don’t support this operation. If you want to perform totally unrelated updates to each element in a range, you can perform point updates for each element in the range and pay a log n cost for each point update.
You can achieve better complexity with a segment tree.
is there any tutorial or something like that, to explain this operation using segment tree ?
I’ve written two posts on segment trees:
They don’t explain this operation directly but combine them with this idea: An update to the tree can be a list of point updates, sorted by index, and we can split this list for left and right children. This should solve a more general problem than a range update: updating any set of indices with any values.
What if I want to update a range with minimum value?
For example if my array is 1 2 3 4 5
and my update query is (l=1,r=5,v=1) then,
for(i=l;i<=r;i++)
arr[i]=min(arr[i],v);
should take place and my final array should be
1 1 1 1 1
Can this be done using BIT?
BITs have one purpose: supporting range sum queries and updates in O(log N) complexity. Sure we can use some hacks to do more with them but we should always try to use a data structure that naturally supports the operations we want to perform. A segment tree will naturally support this operation so you should try to use it.
The explanations are very brief. Examples would make them better
if we’ve non zero elements in input array then how the code will change? specifically in 3rd case Range update and Range queries ?
A rather simple approach is to start with an empty BIT (all elements 0) and then update the value at each index. It’s complexity is O(N log N). I don’t know if there’s a better approach that can do it in O(N).
Question i was trying was.. suppose I/p array is 1 2 3 4 and q queries are there… p 1 2 means print sum from 1 to 2 & u 1 3 4 means add 4 to the elements from 1 to 3… the 3rd case isn’t working on this any idea why ??
Sure it’s working. Use the following code to initialize the BIT:
for (int i = 1; i <= N; ++i) {
scanf("%d", &p);
range_update(i, i, p);
}
if we wanted to change value of array to a specific value i.e. (A[i]…..A[j]) = x , how can we implement that
A straightforward approach is to query for the value in each index of the range and update the difference from the desired value.
Awesome post…Helped me understand the beautiful Fenwick Tree easily.
aweseome tutorial, thanks
Hey, can you please explain how range update point query is working, I am confused on how query(b) is giving the value present at A[b]
The question as I understand is this: why the same query(x) function calculates sum(A[1..x]) for point-update-range-query while it calculates A[x] for range-update-point-query?
update(x,v) and query(x) functions are common to both the cases so they must have the same behavior too. update(x,v) adds v to some elements ft[i] (i≥x) such that when you call query(i) (i≥x), you will see this update v exactly once and thus count it exactly once. query(x) adds some elements ft[i] (i≤x) such that each update to any element i≤x is seen exactly once.
For the point-update-range-query case, all update(x,v) are visible to x’≥x so when you call query(c), you effectively add all the updates applied to all elements 1≤i≤c which is nothing but the sum of A[1..c].
However, in the case of range-update-point-query, updates can be cancelled off. updates(a,b,v) is only visible exactly once inside the range a..b (effected by adding -v to ft[i] for i>b). Now, when you call query(c), it still sums the frequencies from 1 to c but their meaning is now different. If it sees an update v during summing frequencies, it is because that index lied in the range of some range update a..b applied some time before. Since the value is seen only once, it is as if v is added to only that index. This explains why query(c) now calculates A[c]. It is still calculating sum of frequencies but they have a different meaning now.
I hope this makes sense to you.
Hi Kartik,
it all makes sense what you have written above, but you mentioned that frequencies stored in a BIT have different meaning.
ex. Let tree be an array where we represent our BIT
1. in point update – range query: tree[x] represents cumulative frequency for elements with values
{ x – 2^r + 1, … , x } , where r is the position of the right-most non-zero bit. so tree[6] stores cumulative frequency for values 5 and 6. (6 in binary is 110, r=1, 6 – 2^1 + 1 = 5).
but, in range update – point query what does exactly tree[x] represents, what is the meaning of tree[x]?
Thanks in advance.
It basically means the same thing (still a cumulative frequency table) but the semantics are now different.
Suppose you update index 2 with value 5, now when you query for any index >= 2, it’d return 5+whatever it would have returned earlier. You can get the range query behavior as query(a,b) = query(b) – query(a-1).
With range update-point query for an interval [2,4] with update 5, we update index 2 with value 5 and index 5(4+1) with value -5. So if you query for an index x < 2, you won't see the update 5. If you query for 2<=x 4, you’ll see two updates 5 and -5 which cancel each other.
So the meaning of what is stored in an element in a BIT hasn’t changed; what has changed is how we are using it.
Sorry for borthering, but I didn’t formulate my question really well.
I was interested in:
1) what does the stored value in tree[x] means?
ex. In point update – range query tree[6] stores how many times does the values 5 and 6 appear in array.
But in range update – point query the values may be negative.
What do values stored in tree[x] , for range update – point query , mean?
Thanks for replying in such short time.
Oh, you misunderstand what tree[x] stores even in the point update-range query case. tree[6] doesn’t store the count of values 5 and 6 in the whole array. It stores the sum of values at array indices 5 and 6.
It’s illogical to think that a BIT will store count of each value separately because then building a BIT for even a 1-element array could take a billion integers if the updates can be anything. Further, nowhere do we say that the updates must only be positive integers; they can be negative so the array elements can be negative.
So, even in range update-point query, tree[6] stores the sum of values at array indices 5 and 6.
Sir,Do we loose original array when update point or range update,amarite?
BIT doesn’t maintain the updated array for constant time access to its elements. But you can query for the updated value of each element in O(log N).
Sorry I think I was not clear enough.My question was–If we call update like update(i,X) so we have A[i] as A[i]+(X) as new value.For example A[1]=5,A[2]=10,A[3]=15,….calling update(1,5) so now A[1] will be 10.This was my question
Are you saying that you want the original values from the BIT, before any updates were applied to it? No, BIT does not provide that. You can just keep a copy of the original values separately in an array if you want them.
Firstly I would like to apologize for being so dumb sir,but believe me I am facing lot of confusions 😦 .Please answer these question that I am not getting regarding this difficult data structure.
1)When we say update a[i] with x(i.e a[i]+=x) by calling update function,Do we really add anything to the actual array A at index i or we make modifications to the bit tree so that conceptually it will make similar sense like adding x to a[i].
2)Like in this question .https://www.hackerearth.com/problem/algorithm/help-ashu-1/description/
We have to change A[i] to x(see count=0 condition please) so in this case we have to actually call update and change the actual array both.Because we are asked to change actual array.Am I right ?
And again I am very embarrassed to bother you again and again and again.
It’s not a problem. Here goes:
1.) BIT does not update the array as is but makes changes so that a query() call would return the right result. This is to be expected if a DS is supposed to update a range of elements in logarithmic time.
2.) This problem can be easily solved with a BIT but you wouldn’t build the BIT over original array. You should build a BIT over the count of even numbers i.e., for an array [1,2,5,4], you’d build a BIT over [0,1,0,1]. The BIT will allow you to query for the count of even numbers in any range (subtract it from the size of that range to get count of odd numbers). For updates, add 1 to an element if changing it from odd to even and -1 if from even to odd.
I hope that helps. Please do let me know if you need more help.
Sir first of all thanks for such warmth reply 🙂 .
Question link ->https://www.hackerearth.com/problem/algorithm/help-ashu-1/description/
My solution link->https://www.hackerearth.com/submission/2544059/
Sir,I have small doubt left in this question.Please have a look at I will be out of here I swear 😦 .In this question I know how to do when query=1 and query=2.But have small doubt in query=0.In query 0 we are asked to change array at some index l to x(i.e a[l]=x).So we want our original array to get changed.So what we will do is we change our original array a[l] to x as well as our BIT according to changes made in our original array as I did(see my submission).But say we have scenario in which we have query=0 and in that query we are asked to change original array to X for the whole interval like(if query==0 change original array to X for the interval from [L,R] how efficiently we can do this ??)
1.) You didn’t actually have to maintain the original array. You just need to know whether the previous value at an index was even or odd, you could query the BIT for that single index (query(i)-query(i-1)) for that but it would be O(log N).
2.) Change an interval to some value X: You couldn’t do that with a BIT and would have to go for a segment tree (https://kartikkukreja.wordpress.com/2014/11/09/a-simple-approach-to-segment-trees/)
Thankssssss…. Sorry for spamming but I am so much excited now.I finally got it. 🙂 🙂 🙂 🙂 🙂 🙂
Hi,
I took a long time to understand the material.
It makes sense to me if the BIT is only to be operated in 1 of the 3 modes.
Is my thinking right ?
Plainly speaking, if there are a mix of operations, say
operation #1 : point query range update
op #2 : range query point update
op #3 : range query range update
and if I want to perform a mix of these in a random order {op1, op2, op1, op3, op3, …. },
that would not make sense ?
Thanks,
Ravi
Range update range query (mode 3) is superset of the other two modes because a point query/update is also a range query/update where the range contains only that point [i,i].
Point update/query are basically special cases, for which we can optimize as we have in modes 1 and 2.
If you have a mix of operations, you’ll have to use range update-range query.
Nice article. I am also reading your article on segment tree lazy propagation. Is it possible to use BIT to solve the FLIPCOIN problem (which was an example of segment tree lazy propagation)? Thanks.
I don’t think there’s any obvious way to solve FLIPCOIN with BIT. Segment trees are simply more general than BITs and that’s why we were able to solve this with segment trees so easily.
Thank you very much for your reply. I noticed that in the following topcoder tutorial:
https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/#prob
BIT has been used to solve range update point query problem (which is similar but simpler than FLIPCOIN). Is it possible to extend it to solve FLIPCOIN problem?
BIT does support range update-point query or even range update-range query but the updates are basically sums (adding/subtracting some value). FLIPCOIN requires a much more complicated operation: flip (xor with 1) and count. BIT is not suitable for this.
how does the same QUERY code give range sum A[1..p] in case 1 while point value A[p] in case 2 ..could you explain ?
Please look at this comment: https://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree/comment-page-2/#comment-5442
Pingback: Bit fiddling: Exercise that grey matter | Everything Under The Sun
Correct me if I’m wrong! while querying in “Range-update and Point query”, sum should be initialised by A[b] before the loop as b is changing in the loop and finally Sum should be returned
I don’t know if you made the comment before the update but the code has been changed to return the BIT sum + A[b].