Motivation

Given a list of elements,
we want to calculate cumulative total based on an associative binary operation.

Moreover, efficient modification is desired.

Naive

Concept

Using an array arr to store each element in the original list.

Modify

Replace the value with new one.

Query

Sum up the value from the begin to the position.

Complexity

• Initialization:
  $O(N)$
• Modification:
  $O(1)$
• Query:
  $O(N)$
• Space:
  $O(N)$

Prefix Sum Table

Concept

For each position, store the sum from begin to the current position.

Modify

Add the difference to each element in the table from desired position to the end.

Query

It's the value in the position.

Complexity

• Initialization:
  $O(N)$
• Modification:
  $O(N)$
• Query:
  $O(1)$
• Space:
  $O(N)$

Fenwick Tree (Binary Indexed Tree)

Binary Index

Treat the indices (1-based) as binary number.
For each index x,
if the lowest 1 bit is n bits away from LSB (least significant bit),
(i.e. x is ended with n 0's)
then we store the prefix sum of

$2^n$ elements before x (inclusive).

Lowbit

We can get how many element is contained in index x by using lowbit(x).

$\text{lowbit}((11{)}_{10})=\text{lowbit}((1011{)}_2)=(1{)}_2=(1{)}_{10}$

$\text{lowbit}((12{)}_{10})=\text{lowbit}((1100{)}_2)=(100{)}_2=(4{)}_{10}$

We can also get the next node whose range contains x by x + lowbit(x).

$(11{)}_{10}+\text{lowbit}((11{)}_{10})=(12{)}_{10}$

$\text{lowbit}((12{)}_{10})=4\text{, conatains 4 elements, range: }[9,12]$

$(12{)}_{10}+\text{lowbit}((12{)}_{10})=(16{)}_{10}$

$\text{lowbit}((16{)}_{10})=16\text{, conatains 16 elements, range: }[1,16]$

And lowbit can be implemented by

int lowbit(x) { return x & -x; }

Since -x is stored as ~x + 1 in 2's complement.
The 0's are converted into 1 first by ~x,
and then the added 1 causes the 1's carried to the first 0 from LSB,
which is the first 1 from LSB in x,
by using bitwise-and &, only bit that is 1 is the first 1 from LSB.

take x = 964 for example

	$\cdots$	bit 9	bit 8	bit 7	bit 6	bit 5	bit 4	bit 3	bit 2	bit 1	bit 0
x	0	1	1	1	1	0	0	0	1	0	0
~x	1	0	0	0	0	1	1	1	0	1	1
-x	1	0	0	0	0	1	1	1	1	0	0
x & -x	0	0	0	0	0	0	0	0	1	0	0

Modify

Due to the property

if the lowest 1 bit is at the n-th bit from LSB (least significant bit),
(i.e. x is ended with n 0's)
then we store the prefix sum of

$2^n$ elements before it (inclusive).

So if we want to modify the value in index x,
we will need to modify all the positions that its range contains x,
that is, modify the value of x, and replace it by x + lowbit(x) until x >= size.

Query

Again, due to the same property,
if we want to query the prefix sum of x,
we will need to add up the values that are not include in x,
that is, sum up the value of x, and replace it by x - lowbit(x) until x <= 0.

Complexity

• Initialization:
  $O(N)$
• Modification:
  $O(\log N)$
• Query:
  $O(\log N)$
• Space:
  $O(N)$

Sample Code

class FenwickTree {
public:
    FenwickTree(size_t _size) : BIT(_size + 1), size(_size + 1) {}
    
    FenwickTree(const vector<int>& arr)
        : BIT(arr.size() + 1), size(arr.size() + 1) {
        
        for (int i = 1; i < size; ++i) 
            BIT[i] = arr[i - 1];
        
        for (int i = 1; i < size; ++i) {
            int j = i + lowbit(i);
            if (j < size) BIT[j] += BIT[i];
        }
    }
    
    void modify(int x, int value) {
        for (; x < sise; x += lowbit(x))
            BIT[x] += value;
    }
    
    int query(int x) {
        int sum = 0;
        for (; x > 0; x -= lowbit(x)) 
            sum += BIT[x];
        return sum;
    }
    
    int range_query(int from, int to) {
        return query(to) - query(from - 1);
    }
    
private:
    vector<int> BIT;
    size_t size;
    
    inline int lowbit(int x) { return x & -x; }
};