Binary Indexed Tree (Fenwick Tree) - 二分索引木
(Library/DataStructure/BinaryIndexedTree.hpp)

• View this file on GitHub
• Last update: 2025-05-30 20:02:37+09:00
• Include: #include "Library/DataStructure/BinaryIndexedTree.hpp"

Binary Indexed Tree (Fenwick Tree) - 二分索引木

長さ $N$ の数列 $A = (A_1, \dots, A_N)$ に対し、一点加算・区間和取得クエリを効率的に行うことができるデータ構造です。

Function

Constructor

BinaryIndexedTree(int n)

• 数列 $A$ を長さ $n$ で初期化します。初期値はすべて $0$ です。

制約

• $1 \le n \le 10^6$

計算量

• $\textrm{O}(n)$

---

Add

void Add(int i, T v)

• $A_i$ に値 $v$ を加算します。$A_i \leftarrow A_i + v$

制約

• $1 \le i \le n$

計算量

• $\textrm{O}(\log n)$

---

Sum

(1) T Sum(int i)
(2) T Sum(int l, int r)

• (1) 区間 $[1, i]$ の総和を返します。$\sum_{k=1}^{i} A_k$ を計算します。
• (2) 区間 $[l, r]$ の総和を返します。$\sum_{k=l}^{r} A_k$ を計算します。

制約

• (1) $1 \le i \le n$
• (2) $1 \le l \le r \le n$

計算量

• $\textrm{O}(\log n)$

---

Depends on

• Library/Common.hpp

Verified with

• verify/LC-PointAddRangeSum_BIT.test.cpp

Code

#include "../Common.hpp"

template<typename T>
struct BinaryIndexedTree{
    public:
    BinaryIndexedTree(int n) : size_(n){
        data_.resize(size_ + 1, 0);
    }

    T Sum(int i){
        T ret = 0;
        for(; i > 0; i -= i & -i) ret += data_[i];
        return ret;
    }
    
    T Sum(int l, int r){
        return Sum(r) - Sum(l - 1);
    }

    void Add(int i, T v){
        for(; i <= size_; i += i & -i) data_[i] += v;
    }

    private:
    int size_;
    vector<T> data_;
};

#line 2 "Library/Common.hpp"

/**
 * @file Common.hpp
 */

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cstdint>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using ll = int64_t;
using ull = uint64_t;

constexpr const ll INF = (1LL << 62) - (3LL << 30) - 1;
#line 2 "Library/DataStructure/BinaryIndexedTree.hpp"

template<typename T>
struct BinaryIndexedTree{
    public:
    BinaryIndexedTree(int n) : size_(n){
        data_.resize(size_ + 1, 0);
    }

    T Sum(int i){
        T ret = 0;
        for(; i > 0; i -= i & -i) ret += data_[i];
        return ret;
    }
    
    T Sum(int l, int r){
        return Sum(r) - Sum(l - 1);
    }

    void Add(int i, T v){
        for(; i <= size_; i += i & -i) data_[i] += v;
    }

    private:
    int size_;
    vector<T> data_;
};

Back to top page