Fenwick Tree (library/ds/fenwickTree.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-03-25 12:22:53+06:00
• Include: #include "library/ds/fenwickTree.hpp"

overview

Resources

• cp-algorithms
• Youtube - WilliamFiset
• https://nyaannyaan.github.io/library/data-structure/binary-indexed-tree.hpp

Verified with

• library/test/aoj/DSL_2_B-RSQ.fenwick.test.cpp

Code

#pragma once

template <class T> struct FenwickTree { // 1 indexed
    int n;
    vector<T> data;
    FenwickTree() : n(0) {}
    FenwickTree(int n) : n(n), data(n + 1, 0) {}

    // a[id] += x and all the ranges responsible for 'id', O(log(n))
    // x = i&-i => lsb(x); lsb(0b1101000) = 0b1000 = 8
    void add(int id, T x) {
        for (int i = id; i <= n; i += i & -i) {
            data[i] += x;
        }
    }
    void range_add(int l, int r, T val) {
        add(l, val);
        add(r + 1, -val);
    }

    // prefix sum from [1, r], O(log(n))
    T sum(int r) {
        T s(0);
        for (int i = r; i > 0; i -= i & -i) {
            s += data[i];
        }
        return s;
    }
    // [l, r]
    T sum(int l, int r) { return sum(r) - sum(l - 1); }
};

#line 2 "library/ds/fenwickTree.hpp"

template <class T> struct FenwickTree { // 1 indexed
    int n;
    vector<T> data;
    FenwickTree() : n(0) {}
    FenwickTree(int n) : n(n), data(n + 1, 0) {}

    // a[id] += x and all the ranges responsible for 'id', O(log(n))
    // x = i&-i => lsb(x); lsb(0b1101000) = 0b1000 = 8
    void add(int id, T x) {
        for (int i = id; i <= n; i += i & -i) {
            data[i] += x;
        }
    }
    void range_add(int l, int r, T val) {
        add(l, val);
        add(r + 1, -val);
    }

    // prefix sum from [1, r], O(log(n))
    T sum(int r) {
        T s(0);
        for (int i = r; i > 0; i -= i & -i) {
            s += data[i];
        }
        return s;
    }
    // [l, r]
    T sum(int l, int r) { return sum(r) - sum(l - 1); }
};

Back to top page