Fenwick Tree (Binary Indexed Tree)

A Fenwick tree maintains numeric prefix sums while individual array values change. A normal prefix-sum array answers a range sum immediately, but changing one value invalidates many prefixes. A Fenwick tree stores carefully chosen partial sums, giving both point additions and prefix queries in logarithmic time. It is particularly useful when queries and updates are mixed: dynamic frequencies, inversion counting, cumulative scores, or sums of values whose ranks are compressed. The operation must support subtraction if you want arbitrary range sums by subtracting two prefixes. This lesson uses 1-based indices and long long sums; the original array values can be negative.

Prerequisites: Arrays, binary representation, prefix sums.

Build the idea

1. What each cell stores

   Write lowbit(i) = i & -i, the value of the lowest set bit of a positive integer. Cell bit[i] stores the sum of the interval [i-lowbit(i)+1,i]. Thus bit[6] covers positions 5–6, bit[8] covers 1–8, and bit[7] covers position 7 alone. These intervals are not arbitrary: they partition every prefix into disjoint pieces. Use positive signed integers within their representable range for these index operations.

2. Build a prefix query

   To find prefix(7), add bit[7], then bit[6], then bit[4]. The covered intervals are [7,7], [5,6], [1,4], exactly positions 1–7 with no overlap. After using bit[i], subtract lowbit(i) to remove the lowest set bit. At most logarithmically many set bits disappear, so the query is fast. prefix(0) is zero and requires no array access.

3. Update every interval containing a point

   To add delta to position 3, visit indices 3,4,8,... using i += lowbit(i). They are exactly the relevant Fenwick intervals containing that point. For a set-value operation, first compute delta = newValue-oldValue; this implementation deliberately offers additions. The loop must start above zero: add(0,delta) would never advance.

4. A complete small trace

   For [2,1,3,4,5], prefix(4)=10 and prefix(1)=2, so sum(2,4)=8. Adding 6 at position 3 produces [2,1,9,4,5], and the same range now sums to 14. The invariant is preserved because every stored interval containing position 3 receives exactly +6. The program builds by n ordinary additions, favoring clarity over the optional linear-time build.

5. Read the implementation

   The class stores n and bit only; external indices remain 1-based. sum(l,r) uses prefix(r)-prefix(l-1). A tree is not an ordered list of all prefix sums: each internal cell represents its own lowbit-sized interval. Distinguishing those two ideas makes both loops understandable rather than something to memorize. The example uses command A i delta for addition and S l r for a sum.

6. Choosing the right operation

   Suppose a contest gives ten million elements but only a handful of updates. A Fenwick tree is still mathematically valid, but memory and actual workload matter. A static prefix array may be preferable if updates disappear; a segment tree may be preferable if queries require an operation without a convenient inverse. The range formula relies on canceling the contribution of positions before l. Addition permits this cancellation through subtraction; minimum does not.

   Try n=1 explicitly: bit[1] stores the only value, an update touches it once, and a query terminates after one subtraction of lowbit(1). For n=5, an update at 5 visits only 5 before advancing outside the array. The update loop need not reach a power-of-two root covering all n values. Query correctness comes from partitioning the requested prefix, rather than from the existence of one global root cell.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
using namespace std;
struct Fenwick{
    int n;
    vector<long long>bit;
    explicit Fenwick(int n):n(n),bit(n+1,0){
    }
    // bit[i] covers [i-lowbit(i)+1, i]. Update all blocks containing the point.
    void add(int i,long long delta){
        for(;i<=n;i+=i&-i){
            bit[i]+=delta;
        }
    }
    // Remove the last covered block; the remaining prefix ends at i-lowbit(i).
    long long prefix(int i)const{
        long long result=0;
        for(;i>0;i-=i&-i){
            result+=bit[i];
        }
        return result;
    }
    // Subtract the prefix before l to leave exactly the inclusive interval.
    long long sum(int l,int r)const{
        return prefix(r)-prefix(l-1);
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n>>q;
    Fenwick fw(n);
    // Build with ordinary point additions; all external indices are 1-based.
    for(int i=1;i<=n;i++){
        long long x;
        cin>>x;
        fw.add(i,x);
    }
    while(q--){
        char op;
        cin>>op;
        if(op=='A'){
            int i;
            long long d;
            cin>>i>>d;
            fw.add(i,d);
        }
        else{
            int l,r;
            cin>>l>>r;
            cout<<fw.sum(l,r)<<'\n';
        }
    }
}

Complexity analysis

Preprocessing: O(n log n) in this implementation. Point addition and prefix/range sum: O(log n), because each loop changes the relevant lowest set bit. Storage: O(n).

Example input and output

n q, then n values. Each of q commands is A i delta or S l r. Require n≥1, valid indices, and sums fitting long long.

Input

5 3
2 1 3 4 5
S 2 4
A 3 6
S 2 4

Output

8
14

The first range contains 1+3+4=8. Increasing the third value by 6 changes that sum to 14.

Practical applications

Dynamic range sums; inversion counting after coordinate compression; frequency tables; Euler-tour subtree sums after flattening a tree.

Check your understanding

What interval is represented by bit[12]?

Put it into practice

Extend the program with SET i x while keeping each operation logarithmic.