Fenwick Tree
(library/segtree/fenwick_tree.hpp)

• View this file on GitHub
• Last update: 2026-01-20 20:11:22+09:00
• Include: #include "library/segtree/fenwick_tree.hpp"

Fenwick Tree

できること

• 1点に加算する
• 区間[0, i]の和を取得

計算量

• 構築: $O(N)$
• 1点更新add: $O(logN)$
• 区間取得sum: $O(logN)$

使い方

FenwickTree fwk(N);

Required by

• 統合セグ木 (library/segtree/unified_segment_tree.hpp)
• 転倒数 (library/sequence/inversion_number.hpp)
• 区間の値の種類数 (library/sequence/static_range_count_distinct.hpp)

Verified with

• Fenwick Treeのテスト:RSQ (tests/segtree.fenwick_tree.test.cpp)
• 統合セグ木のテスト:RMQ RAQ (tests/segtree.unified_segment_tree.test.cpp)
• 転倒数・座標圧縮・FenwickTreeのテスト (tests/sequence.inversion_number.test.cpp)
• 区間の値の種類数のテスト (tests/sequence.static_range_count_distinct.test.cpp)
• Mo's algorithmのテスト (tests/various.mo.test.cpp)

Code

#pragma once
struct FenwickTree {
  private:
    int N;
    vector<int> fwk;

  public:
    FenwickTree(int N) : N(N) { fwk.assign(N + 1, 0); }
    FenwickTree(const vector<int> &A) : N(A.size()) {
        fwk.assign(N + 1, 0);
        for (int i = 1; i <= N; ++i) {
            fwk[i] += A[i - 1];
            if (i + (i & -i) <= N) fwk[i + (i & -i)] += fwk[i];
        }
    }
    void add(int i, const int &x) {
        for (++i; i <= N; i += i & -i) fwk[i] += x;
    }
    int sum(int i) {
        int ans = 0;
        for (++i; i; i -= i & -i) ans += fwk[i];
        return ans;
    }
};

#line 2 "library/segtree/fenwick_tree.hpp"
struct FenwickTree {
  private:
    int N;
    vector<int> fwk;

  public:
    FenwickTree(int N) : N(N) { fwk.assign(N + 1, 0); }
    FenwickTree(const vector<int> &A) : N(A.size()) {
        fwk.assign(N + 1, 0);
        for (int i = 1; i <= N; ++i) {
            fwk[i] += A[i - 1];
            if (i + (i & -i) <= N) fwk[i + (i & -i)] += fwk[i];
        }
    }
    void add(int i, const int &x) {
        for (++i; i <= N; i += i & -i) fwk[i] += x;
    }
    int sum(int i) {
        int ans = 0;
        for (++i; i; i -= i & -i) ans += fwk[i];
        return ans;
    }
};

Back to top page