Fenwick-Tree
(segtree/fenwick-tree.cpp)

• View this file on GitHub
• Last update: 2021-04-08 19:35:44+09:00

説明

長さ $n$ の配列を管理するデータ構造

数でなくても、群なら OK

• FenwickTree(n): 長さ $n$、全要素 $0$ で初期化
• add(p, x): a[p] += x を行う
• sum(l, r): a[l] + a[l + 1] + ... + a[r - 1] を返す

計算量

• FenwickTree(n): $O(n)$
• クエリ: $O(\log n)$

Verified with

• test/AOJ-DLS-2-B.test.cpp
• test/yosupo-point-add-range-sum.test.cpp

Code

#pragma once

#include <bits/stdc++.h>
using namespace std;

template <typename T>
class FenwickTree {
private:
    int _n;
    vector<T> data;

    T sum(int r) {
        T s = 0;
        while(r > 0) {
            s += data[r - 1];
            r -= r & -r;
        }
        return s;
    }

public:
    FenwickTree() = default;
    explicit FenwickTree(int n) : _n(n), data(n) {}

    void add(int p, T x) {
        assert(0 <= p && p < _n);
        p++;
        while(p <= _n) {
            data[p - 1] += x;
            p += p & -p;
        }
    }

    T sum(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        return sum(r) - sum(l);
    }
};
/*
 * @brief Fenwick-Tree
 * @docs docs/fenwick-tree.md
 */

#line 2 "segtree/fenwick-tree.cpp"

#include <bits/stdc++.h>
using namespace std;

template <typename T>
class FenwickTree {
private:
    int _n;
    vector<T> data;

    T sum(int r) {
        T s = 0;
        while(r > 0) {
            s += data[r - 1];
            r -= r & -r;
        }
        return s;
    }

public:
    FenwickTree() = default;
    explicit FenwickTree(int n) : _n(n), data(n) {}

    void add(int p, T x) {
        assert(0 <= p && p < _n);
        p++;
        while(p <= _n) {
            data[p - 1] += x;
            p += p & -p;
        }
    }

    T sum(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        return sum(r) - sum(l);
    }
};
/*
 * @brief Fenwick-Tree
 * @docs docs/fenwick-tree.md
 */

Back to top page