The Fenwick Tree (BIT)

Lesson 10 of 11 · Data structures

A Fenwick tree (Binary Indexed Tree) maintains an array and answers the question "what is the sum of the first k elements?" – even while the elements change. Both operations take O(log n), and the code is short: about ten lines.

Before you start: prerequisites – Data structures – guide.
How to learn: type in and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.

The problem: sums with updates

An array of n numbers and q queries of two kinds are given: change the element at position i and what is the sum on the interval [l, r]. An ordinary array gives an update in O(1) and a sum in O(n). Prefix sums give a sum in O(1) but an update in O(n). For n, q up to 2·105 both approaches are too slow, while a Fenwick tree does both queries in O(log n).

The idea: lowbit

The positions are from 1 to n. The element bit[i] keeps the sum of the part of the array that ends at i, and the length of that part is the lowest bit of the number i: lowbit(i) = i & (-i). For example, bit[12] keeps the sum of positions 9–12 (12 = 1100₂, the lowest bit is 4), and bit[7] only position 7.

  • The sum of the first i: add bit[i], then go to i -= lowbit(i), while i > 0.
  • Add x to position i: add x to bit[i], then go to i += lowbit(i), while i ≤ n.

In both cases the number of steps is at most the number of bits, i.e. O(log n).

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<long long> bit;

void add(int i, long long x) {            // a[i] += x
    for (; i <= n; i += i & (-i)) bit[i] += x;
}

long long prefixSum(int i) {              // a[1] + ... + a[i]
    long long s = 0;
    for (; i > 0; i -= i & (-i)) s += bit[i];
    return s;
}

int main() {
    int q;
    cin >> n >> q;
    bit.assign(n + 1, 0);
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) { cin >> a[i]; add(i, a[i]); }
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {                  // 1 i v : a[i] = v
            int i; long long v;
            cin >> i >> v;
            add(i, v - a[i]);             // we add the difference
            a[i] = v;
        } else {                          // 2 l r : the sum a[l..r]
            int l, r;
            cin >> l >> r;
            cout << prefixSum(r) - prefixSum(l - 1) << "\n";
        }
    }
    return 0;
}

The update "set to v" is turned into "add the difference v − a[i]", which is why we also keep the array a itself.

When a Fenwick tree, and when a segment tree?

A Fenwick tree is shorter and faster, but it naturally works only for operations that have an "inverse" (sum – subtraction, XOR). For the minimum, the maximum or more complex queries on an interval, a segment tree is used.

Practice tasks

Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.

TASK 01Difficulty: harder

The number of inversions

An array of n different numbers from 1 to n is given (a permutation, n ≤ 2·105). An inversion is a pair i < j for which a[i] > a[j]. How many inversions are there?

Example

Input

5
2 4 1 3 5

Output

3
TASK 02Difficulty: medium

Sales by days

A shop records sales for n days (initially 0). Queries: A d k – on day d another k items were sold; S a b – how many items were sold in total from day a to day b?

Example

Input

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

Output

3
8
Common mistakes and tips
  • A Fenwick tree uses positions from 1; for positions from 0 add 1 in every call.
  • The sum on the interval [l, r] is prefixSum(r) − prefixSum(l − 1).
  • Turn "set a value" into "add the difference" and keep the current array.
  • Sums easily overflow int – use long long.

Check your knowledge

Open the quiz

Mini quiz: the Fenwick tree

1. What is 12 & (-12)?




2. What is the complexity of a query for the sum of the first k elements?




3. Which query does a Fenwick tree not support directly?