Binary Indexed Tree
(datastructure/binaryindexedtree.hpp)

• View this file on GitHub
• Last update: 2020-08-25 17:20:34+09:00
• Include: #include "datastructure/binaryindexedtree.hpp"

概要

一点加算クエリと区間和クエリを対数時間で行うデータ構造.

計算量

• 構築 : $O(n)$
• 区間取得 : $O(\log n)$
• 二分探索 : $O(\log n)$

使用例

• BinaryIndexedTree<int> bit(N) : 要素数$N$のBIT
• bit.add(k, x) : $k$要素目に$x$を加算.
• bit.sum(k) : 閉区間$[0, k]$の和を求める
• bit.sum(l, r) : 半開区間$[l, r)$の和を求める

Verified with

• test/aoj/DSL_2_B.binaryindexedtree.test.cpp
• test/yukicoder/1115.test.cpp

Code

/**
* @brief Binary Indexed Tree
* @docs docs/datastructure/binaryindexedtree.md
*/

template <typename T>
struct BinaryIndexedTree {
    vector<T> data;
    BinaryIndexedTree(int sz) { data.assign(++sz, 0); }
    T sum(int k) {
        if (k < 0) return T(0);
        T ret = 0;
        for (++k; k > 0; k -= k & -k) ret += data[k];
        return (ret);
    }
    T sum(int l, int r) {
        assert(l <= r);
        return sum(r - 1) - sum(l - 1);
    }
    void add(int k, T x) {
        for (++k; k < data.size(); k += k & -k) data[k] += x;
    }
};

#line 1 "datastructure/binaryindexedtree.hpp"
/**
* @brief Binary Indexed Tree
* @docs docs/datastructure/binaryindexedtree.md
*/

template <typename T>
struct BinaryIndexedTree {
    vector<T> data;
    BinaryIndexedTree(int sz) { data.assign(++sz, 0); }
    T sum(int k) {
        if (k < 0) return T(0);
        T ret = 0;
        for (++k; k > 0; k -= k & -k) ret += data[k];
        return (ret);
    }
    T sum(int l, int r) {
        assert(l <= r);
        return sum(r - 1) - sum(l - 1);
    }
    void add(int k, T x) {
        for (++k; k < data.size(); k += k & -k) data[k] += x;
    }
};

Back to top page