Range updates with BIT / Fenwick Tree

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.

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.

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


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.


76 thoughts on “Range updates with BIT / Fenwick Tree

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

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

    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.

    • 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 ??

  2. if we wanted to change value of array to a specific value i.e. (A[i]…..A[j]) = x , how can we implement that

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

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

  4. 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 ??)

  5. 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 ?


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

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

  7. Pingback: Bit fiddling: Exercise that grey matter | Everything Under The Sun

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s