fenwick tree
(data_structure/fenwick_tree.hpp)

• View this file on GitHub
• Last update: 2023-09-10 00:45:18+09:00
• Include: #include "data_structure/fenwick_tree.hpp"

説明

配列 $a$ に対して、$1$ 点加算、区間和が $O(\log N)$ でできるデータ構造。

add(int p, T x)

a[p] に $x$ を加算

prefix_sum(int p)

sum(a[0], …, a[p-1]) を返す。

sum(int l, int r)

sum(a[l], …, a[r-1]) を返す。

lower_bound(T key)

$prefix_sum(x) \geq key$ となる最小のxを返す関数 O(log N)

Required by

• Static Rectangle Sum (data_structure/static_rectangle_sum.hpp)
• Inversion Number (math/inversion_number.hpp)

Verified with

• test/data_structure/Point_Add_Range_Sum_BIT.test.cpp
• test/data_structure/Static_Range_Inversion_Query.test.cpp
• test/data_structure/Static_Rectangle_Sum.test.cpp
• test/geometry/segment_intersection.test.cpp
• test/math/Inversion_Number.test.cpp

Code

#pragma once

#include <cassert>

#include <vector>


namespace ebi {

template <class T> struct fenwick_tree {
  private:
    int n;
    std::vector<T> data;

  public:
    fenwick_tree(int _n) : n(_n), data(std::vector<T>(_n + 1, T(0))) {}

    void add(int i, T val) {
        i++;
        for (int x = i; x <= n; x += x & -x) {
            data[x] += val;
        }
    }

    T prefix_sum(int i) const {
        assert(0 <= i && i <= n);
        T ret = 0;
        for (int x = i; x > 0; x -= x & -x) {
            ret += data[x];
        }
        return ret;
    }

    T sum(int l, int r) const {
        return prefix_sum(r) - prefix_sum(l);
    }

    T all_sum() const {
        return prefix_sum(n);
    }

    // prefix_sum(x) >= key となる最小のxを返す関数 O(log N)

    int lower_bound(T key) {
        if (key <= 0) return 0;
        int x = 0;
        int max = 1;
        while ((max << 1) <= n) max <<= 1;
        for (int k = max; k > 0; k >>= 1) {
            if (x + k <= n && data[x + k] < key) {
                x += k;
                key -= data[x];
            }
        }
        return x + 1;
    }
};

}  // namespace ebi

#line 2 "data_structure/fenwick_tree.hpp"

#include <cassert>

#include <vector>


namespace ebi {

template <class T> struct fenwick_tree {
  private:
    int n;
    std::vector<T> data;

  public:
    fenwick_tree(int _n) : n(_n), data(std::vector<T>(_n + 1, T(0))) {}

    void add(int i, T val) {
        i++;
        for (int x = i; x <= n; x += x & -x) {
            data[x] += val;
        }
    }

    T prefix_sum(int i) const {
        assert(0 <= i && i <= n);
        T ret = 0;
        for (int x = i; x > 0; x -= x & -x) {
            ret += data[x];
        }
        return ret;
    }

    T sum(int l, int r) const {
        return prefix_sum(r) - prefix_sum(l);
    }

    T all_sum() const {
        return prefix_sum(n);
    }

    // prefix_sum(x) >= key となる最小のxを返す関数 O(log N)

    int lower_bound(T key) {
        if (key <= 0) return 0;
        int x = 0;
        int max = 1;
        while ((max << 1) <= n) max <<= 1;
        for (int k = max; k > 0; k >>= 1) {
            if (x + k <= n && data[x + k] < key) {
                x += k;
                key -= data[x];
            }
        }
        return x + 1;
    }
};

}  // namespace ebi

Back to top page