Binary Indexed Tree
(lib/data_structure/binary_indexed_tree.hpp)

• View this file on GitHub
• Last update: 2024-11-15 16:06:01+09:00
• Include: #include "lib/data_structure/binary_indexed_tree.hpp"

Binary Indexed Tree

使い方

• BinaryIndexedTree<T>(N): 要素数 $N$ のBITを構築します。
• add(i, x): i 番目の要素に x を加算します。
• get(i): i 番目の要素を取得します。
• sum(i): 区間 [0, i)の和を取得します。
• sum(l, r): 区間 [l, r) の和を取得します。
• lower_bound(x): 要素が全て非負である時、[0, k)の区間和が x 以上となるような最小の k を求めます。
• upper_bound(x): 要素が全て非負である時、[0, k)の区間和が x より大きくなるような最小の k を求めます。

計算量

• add(i, x): $\mathrm{O}(\log N)$
• get(i): $\mathrm{O}(\log N)$
• sum(i): $\mathrm{O}(\log N)$
• sum(l, r): $\mathrm{O}(\log N)$
• lower_bound(x): $\mathrm{O}(\log N)$
• upper_bound(x): $\mathrm{O}(\log N)$

Verified with

• test/library_checker/data_structure/point_add_range_sum.test.cpp
• test/library_checker/data_structure/range_kth_smallest.test.cpp
• test/library_checker/data_structure/static_range_inversions_query.test.cpp
• test/library_checker/tree/vertex_add_path_sum.test.cpp
• test/library_checker/tree/vertex_add_subtree_sum.test.cpp

Code

#pragma once

/**
 * @brief Binary Indexed Tree
 * @docs docs/data_structure/binary_indexed_tree.md
 */

#include <vector>

template <typename T>
struct BinaryIndexedTree{
    int N;
    std::vector<T> BIT;
    BinaryIndexedTree(const int N) : N(N), BIT(N + 1, 0){
    }

    T get(int i){
        return sum(i + 1) - sum(i);
    }

    void add(int i, T x){
        i++;
        while(i <= N){
            BIT[i] += x;
            i += i & -i;
        }
    }

    T sum(int i) const {
        T ans = 0;
        while(i > 0){
            ans += BIT[i];
            i -= i & -i;
        }
        return ans;
    }

    T sum(int L, int R) const {
        return sum(R) - sum(L);
    }

    int lower_bound(T x) const {
        if(x <= 0){
            return 0;
        } else{
            int v = 0, r = 1;
            while(r < N) r = r << 1;
            for(int len = r; len > 0; len = len >> 1){
                if(v + len < N && BIT[v + len] < x){
                    x -= BIT[v + len];
                    v += len;
                }
            }
            return v;
        }
    }

    int upper_bound(T x) const {
        if(x < 0){
            return 0;
        } else{
            int v = 0, r = 1;
            while(r <= N) r = r << 1;
            for(int len = r; len > 0; len = len >> 1){
                if(v + len <= N && BIT[v + len] <= x){
                    x -= BIT[v + len];
                    v += len;
                }
            }
            return v;
        }
    }

    T operator [](int i) const {
        return sum(i, i + 1);
    }
};

#line 2 "lib/data_structure/binary_indexed_tree.hpp"

/**
 * @brief Binary Indexed Tree
 * @docs docs/data_structure/binary_indexed_tree.md
 */

#include <vector>

template <typename T>
struct BinaryIndexedTree{
    int N;
    std::vector<T> BIT;
    BinaryIndexedTree(const int N) : N(N), BIT(N + 1, 0){
    }

    T get(int i){
        return sum(i + 1) - sum(i);
    }

    void add(int i, T x){
        i++;
        while(i <= N){
            BIT[i] += x;
            i += i & -i;
        }
    }

    T sum(int i) const {
        T ans = 0;
        while(i > 0){
            ans += BIT[i];
            i -= i & -i;
        }
        return ans;
    }

    T sum(int L, int R) const {
        return sum(R) - sum(L);
    }

    int lower_bound(T x) const {
        if(x <= 0){
            return 0;
        } else{
            int v = 0, r = 1;
            while(r < N) r = r << 1;
            for(int len = r; len > 0; len = len >> 1){
                if(v + len < N && BIT[v + len] < x){
                    x -= BIT[v + len];
                    v += len;
                }
            }
            return v;
        }
    }

    int upper_bound(T x) const {
        if(x < 0){
            return 0;
        } else{
            int v = 0, r = 1;
            while(r <= N) r = r << 1;
            for(int len = r; len > 0; len = len >> 1){
                if(v + len <= N && BIT[v + len] <= x){
                    x -= BIT[v + len];
                    v += len;
                }
            }
            return v;
        }
    }

    T operator [](int i) const {
        return sum(i, i + 1);
    }
};

Back to top page