Binary Indexed Tree
(data-structure/binary-indexed-tree/BinaryIndexedTree.hpp)

• View this file on GitHub
• Last update: 2024-11-18 02:13:41+09:00
• Include: #include "data-structure/binary-indexed-tree/BinaryIndexedTree.hpp"

概要

todo

計算量

todo

Verified with

• verify/LibraryChecker/data-structure/binary-indexed-tree/PointAddRangeSum.test.cpp

Code

template <class T>
struct fenwick_tree {
   public:
    fenwick_tree() : _n(0) {}
    explicit fenwick_tree(int n) : _n(n), data(n) {}

    void add(int p, T x) {
        p++;
        while (p <= _n) {
            data[p - 1] += x;
            p += p & -p;
        }
    }

    T sum(int l, int r) {
        return sum(r) - sum(l);
    }

   private:
    int _n;
    vector<T> data;

    T sum(int r) {
        T s = 0;
        while (r > 0) {
            s += data[r - 1];
            r -= r & -r;
        }
        return s;
    }
};

#line 1 "data-structure/binary-indexed-tree/BinaryIndexedTree.hpp"

template <class T>
struct fenwick_tree {
   public:
    fenwick_tree() : _n(0) {}
    explicit fenwick_tree(int n) : _n(n), data(n) {}

    void add(int p, T x) {
        p++;
        while (p <= _n) {
            data[p - 1] += x;
            p += p & -p;
        }
    }

    T sum(int l, int r) {
        return sum(r) - sum(l);
    }

   private:
    int _n;
    vector<T> data;

    T sum(int r) {
        T s = 0;
        while (r > 0) {
            s += data[r - 1];
            r -= r & -r;
        }
        return s;
    }
};

Back to top page