Introduction

What is Fenwick Tree ?

A Fenwick Tree (also called Binary Indexed Tree) is a data structure that supports sum range queries as well as setting values in a static array and getting the value of the prefix sum up some index efficiently.

Complexity

Implementation

Video Explanation: Click here

class Fenwick {
public:
    int n;
    vector<long long> bit;

    Fenwick(int n) {
        this->n = n;
        bit.assign(n + 1, 0); // 1-indexed
    }

    // Add delta to index idx.
    void update(int idx, long long delta) {
        while (idx <= n) {
            bit[idx] += delta;
            idx += idx & -idx; // move to next range containing idx.
        }
    }

    // Prefix sum [1...idx].
    long long query(int idx) {
        long long sum = 0;
        while (idx > 0) {
            sum += bit[idx];
            idx -= idx & -idx; // move to previous range.
        }
        return sum;
    }

    // Range sum [l...r].
    long long query(int l, int r) {
        return query(r) - query(l - 1);
    }

    // Set arr[idx] = val (optional helper).
    void setValue(int idx, long long val) {
        long long curr = query(idx, idx);
        update(idx, val - curr);
    }
};

Usage

Fenwick ft(5);

// Array: [1,2,3,4,5]
ft.update(1, 1);
ft.update(2, 2);
ft.update(3, 3);
ft.update(4, 4);
ft.update(5, 5);

cout << ft.query(3);      // 6 (1+2+3)
cout << ft.query(2, 4);   // 9 (2+3+4)

ft.update(3, 5);          // arr[3] += 5

cout << ft.query(2, 4);   // 14 (2+8+4)