BIT
(src/DataStructure/BIT.hpp)

• View this file on GitHub
• Last update: 2023-11-12 21:52:10+09:00
• Include: #include "src/DataStructure/BIT.hpp"

BIT

要素数が $N$ の区間に対して

• 要素の $1$ 点更新
• 区間の要素の総和

を $O(log N)$ で求めることができるデータ構造です。

コンストラクタ

BIT<T> (int N)

長さ $N$ で値が 0 の区間を生成します。

計算量

$O(N)$

add(int p, T x)

区間 $p$ に $x$ を加算します。

計算量

$O(log N)$

sum(int idx)

区間 $[0, idx)$ の総和を返します

計算量

$O(log N)$

sum(int l, int r)

区間 $[l, r)$ の総和を返します

計算量

$O(log N)$

Verified with

• test/DataStructure/BIT_Point_Add_Range_Sum.test.cpp

Code

#pragma once

#include <cassert>
#include <functional>
#include <iostream>
#include <vector>

namespace lib {
template <class T>
class BIT {
   public:
    BIT(int N) : _N(N), _bit(_N) {}
    void add(int idx, T value) {
        assert(0 <= idx && idx < _N);
        idx++;
        while (idx <= _N) {
            _bit[idx - 1] += value;
            idx += idx & -idx;
        }
    }

    T sum(int idx) {
        assert(0 <= idx && idx <= _N);
        T value = 0;
        while (idx > 0) {
            value += _bit[idx - 1];
            idx -= idx & -idx;
        }
        return value;
    }

    T sum(int l, int r) {
        assert(0 <= l && l <= r && r <= _N);
        return sum(r) - sum(l);
    }

   private:
    int _N;
    std::vector<T> _bit;
};
}  // namespace lib

#line 2 "src/DataStructure/BIT.hpp"

#include <cassert>
#include <functional>
#include <iostream>
#include <vector>

namespace lib {
template <class T>
class BIT {
   public:
    BIT(int N) : _N(N), _bit(_N) {}
    void add(int idx, T value) {
        assert(0 <= idx && idx < _N);
        idx++;
        while (idx <= _N) {
            _bit[idx - 1] += value;
            idx += idx & -idx;
        }
    }

    T sum(int idx) {
        assert(0 <= idx && idx <= _N);
        T value = 0;
        while (idx > 0) {
            value += _bit[idx - 1];
            idx -= idx & -idx;
        }
        return value;
    }

    T sum(int l, int r) {
        assert(0 <= l && l <= r && r <= _N);
        return sum(r) - sum(l);
    }

   private:
    int _N;
    std::vector<T> _bit;
};
}  // namespace lib

Back to top page