【Algorithm Notes】Fenwick Tree/Binary Indexed Tree

Translation Notice
This article was machine-translated using DeepSeek-R1.

Original Version: Authored in Chinese by myself

Accuracy Advisory: Potential discrepancies may exist between translations

Precedence: The Chinese text shall prevail in case of ambiguity

Feedback: Technical suggestions regarding translation quality are welcomed

Introduction

The Fenwick Tree, also known as Binary Indexed Tree (BIT), is a tree-like data structure. Despite its name, its applications often seem unrelated to trees:

Given a sequence $A=(A_1,A_2,\dots,A_N)$, perform the following operations in $\mathcal O(\log N)$ time:
$\to~$Calculate the sum of all elements in the interval $[L,R]$.
$\to~$Update a specific element $A_x$ by adding $k$.

To optimize summation, prefix sums come to mind, offering $\mathcal O(1)$ query time but $\mathcal O(N)$ update time. Conversely, naively storing all elements allows $\mathcal O(1)$ updates but $\mathcal O(N)$ queries. The solution? The Fenwick Tree.

Basic Algorithm

Luogu P3374 “Fenwick Tree 1 Template”
Constraints: $1\le n,m\le 10^5$, where $m$ is the total number of operations.

With $n,m\le 10^5$, an $\mathcal O(nm)$ brute-force approach is infeasible. The Fenwick Tree achieves $\mathcal O(M\log N)$ time. Its structure is illustrated below:
Fenwick Tree Structure

Let $B$ represent the internal storage. From the diagram:

$B_1=A_1$
$B_2=A_1+A_2$
$B_3=A_3$
$B_4=A_1+A_2+A_3+A_4$
…

Here, $B_i$ stores the sum $A_{i-2^k+1}+A_{i-2^k+2}+\dots+A_i$, where $k$ is the number of trailing zeros in $i$’s binary representation. This $2^k$ is the lowbit of $i$.

About the lowbit Function
$\to~$Definition:

$\mathrm{lowbit}(0)$ is undefined.

For $x > 0$, $\mathrm{lowbit}(x)=2^k$, where $k$ is the number of trailing zeros in $x$’s binary representation.

$\to~$Examples: $\mathrm{lowbit}(10010_2)=10_2$; $\mathrm{lowbit}(10000_2)=10000_2$
$\to~$C/C++ Implementation:
1
2
3
inline int lowbit(int x) {
    return x & -x;
}
Or as a macro:
1
#define lowbit(x) (x) & -(x)

$$ l:=i-\mathrm{lowbit}(i)+1\\ r:=i\\ B_i=\sum_{j=l}^{r} A_j $$

This allows $\mathcal O(\log n)$ prefix sums (prefixSum(x)) and updates (update(x, k)). Interval sums $[L,R]$ are computed as segmentSum(l, r) = prefixSum(r) - prefixSum(l - 1). Code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50


#include <cstdio>
using namespace std;

template <typename value_type>
class fenwick_tree {
private:
    const int n;
    value_type* a;
    inline int lowbit(int x) { return x & -x; }
public:
    inline fenwick_tree(int m): n(m) {
        a = new value_type[n + 1];
        for(int i=0; i<=n; i++)
            a[i] = 0;
    }
    inline ~fenwick_tree() { delete[] a; }
    inline value_type prefixSum(int i) {
        value_type res = 0;
        for(; i; i-=lowbit(i)) res += a[i];
        return res;
    }
    inline value_type segmentSum(int l, int r) {
        return prefixSum(r) - prefixSum(l - 1);
    }
    inline void update(int i, const value_type& d) {
        for(; i<=n; i+=lowbit(i))
            a[i] += d;
    }
};

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    fenwick_tree<int> bit(n);
    for(int i=1; i<=n; i++)
    {
        int a;
        scanf("%d", &a);
        bit.update(i, a);
    }
    while(m--)
    {
        int op, x, y;
        scanf("%d%d%d", &op, &x, &y);
        if(op == 1) bit.update(x, y);
        else printf("%d\n", bit.segmentSum(x, y));
    }
    return 0;
}

On Luogu P3374, this code runs in $572\mathrm{ms}$, compared to ~$2.5\mathrm{s}$ for a segment tree implementation, highlighting the Fenwick Tree’s efficiency.

Extended Applications

Knowledge Prerequisite: Discretization
Given a sequence $A$, discretization maps elements to $[1,N]$ while preserving order. For $A=(A_1,\dots,A_N)$, discretized sequence $B=(B_1,\dots,B_N)$ satisfies:

$1\le B_i\le N$
$A_i < A_j \Rightarrow B_i < B_j$, $A_i = A_j \Rightarrow B_i = B_j$, $A_i > A_j \Rightarrow B_i > B_j$.

Counting Inversions

Inversion pairs can be counted using a Fenwick Tree after discretization.

Luogu P1908 Inversion Pairs
Given $A=(A_1,\dots,A_N)$, count pairs $(i,j)$ where $i A_j$. Constraints: $N\le 10^5, A_i\le 10^9$.

After discretizing $A$ to $B$, use a Fenwick Tree to track occurrences. Traverse $B$ while maintaining a running count of elements ≤ current $B_i$, subtracting from the total possible pairs $\frac{N(N-1)}{2}$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58


#include <cstdio>
#include <algorithm>
#define maxn 500005
using namespace std;

inline int read() {
    static char c;
    while((c = getchar()) < '0' && c > '9');
    int res = c ^ 48;
    while((c = getchar()) >= '0' && c <= '9')
        res = (res << 3) + (res << 1) + (c ^ 48);
    return res;
}

template <typename value_type>
class fenwick_tree {
private:
    const int n;
    value_type* a;
    inline int lowbit(int x) { return x & -x; }
public:
    inline fenwick_tree(int m): n(m) {
        a = new value_type[n + 1];
        for(int i=0; i<=n; i++)
            a[i] = 0;
    }
    inline ~fenwick_tree() { delete[] a; }
    inline value_type prefixSum(int i) {
        value_type res = 0;
        for(++i; i; i-=lowbit(i)) res += a[i];
        return res;
    }
    inline void update(int i, const value_type& d) {
        for(++i; i<=n; i+=lowbit(i))
            a[i] += d;
    }
};

int a[maxn], rk[maxn];

int main()
{
    int n = read();
    for(int i=0; i<n; i++)
        a[rk[i] = i] = read();
    stable_sort(rk, rk + n, [&](int x, int y) -> bool {
        return a[x] < a[y];
    }); // Use stable_sort to handle duplicates
    fenwick_tree<int> bit(n);
    long long ans = n * (n - 1LL) >> 1LL;
    for(int i=0; i<n; i++)
    {
        ans -= bit.prefixSum(rk[i]); // Subtract non-inversion pairs
        bit.update(rk[i], 1); // Dynamically update occurrence count
    }
    printf("%lld\n", ans);
    return 0;
}

Exercise: CF1676H2 Maximum Crossings (Hard Version)

Range Updates

While Fenwick Trees don’t directly support range updates, difference arrays can help:

Luogu P3368 “Fenwick Tree 2 Template”
Operations:

1 x y k: Add $k$ to all elements in $[x,y]$.

2 x: Query the value at $A_x$.

Maintain a difference array $B$ where $B_i = A_i - A_{i-1}$. Range updates become:

$B_x \mathrel{+}=k$
$B_{y+1} \mathrel{-}=k$

Querying $A_x$ is equivalent to summing $B_1$ to $B_x$ via prefixSum(x).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57


#include <cstdio>
#define maxn 500005
using namespace std;

template <typename value_type>
class fenwick_tree {
private:
    const int n;
    value_type* a;
    inline int lowbit(int x) { return x & -x; }
public:
    inline fenwick_tree(int m): n(m) {
        a = new value_type[n + 1];
        for(int i=0; i<=n; i++)
            a[i] = 0;
    }
    inline ~fenwick_tree() { delete[] a; }
    inline value_type prefixSum(int i) {
        value_type res = 0;
        for(; i; i-=lowbit(i)) res += a[i];
        return res;
    }
    inline void update(int i, const value_type& d) {
        for(; i<=n; i+=lowbit(i))
            a[i] += d;
    }
};

int a[maxn];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++)
        scanf("%d", a + i);
    fenwick_tree<int> bit(n);
    while(m--)
    {
        int op;
        scanf("%d", &op);
        if(op == 1)
        {
            int l, r, k;
            scanf("%d%d%d", &l, &r, &k);
            bit.update(l, k);
            if(r < n) bit.update(r + 1, -k);
        }
        else
        {
            int x;
            scanf("%d", &x);
            printf("%d\n", a[x] + bit.prefixSum(x));
        }
    }
    return 0;
}

Exercises

Luogu P1168 Median (Finding the $k$-th largest)
Luogu P1637 Triples
Luogu P6477 Subsequence Issues
Luogu P8253 Correct Sorting
ABC256 F - Cumulative Cumulative Cumulative Sum
Luogu P3372 Segment Tree Template (Try a “Super Fenwick Tree” approach?)

Conclusion

The Fenwick Tree efficiently handles point updates and prefix sums. Questions and suggestions are welcome!
~~Please like and share!~~