---
tags: Data Structure
title: Fenwick Tree
---

## 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`](https://en.wikipedia.org/wiki/Two'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<br>&<br>-x | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | <font color="orange">1</font> | <font color="orange">0</font> | <font color="orange">0</font> |

### 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; }
};