cp-library

C++ Library for Competitive Programming

View the Project on GitHub emthrm/cp-library

:heavy_check_mark: 区間加算クエリ対応 Fenwick tree
(include/emthrm/data_structure/fenwick_tree/fenwick_tree_supporting_range_add_query.hpp)

Fenwick tree (binary indexed tree)

時間計算量

  時間計算量
Fenwick tree $\langle O(N), O(\log{N}) \rangle$
2次元 Fenwick tree $\langle O(HW), O((\log{H})(\log{W})) \rangle$

仕様

Fenwick tree

template <typename Abelian>
struct FenwickTree;

メンバ関数

名前 効果・戻り値 要件
explicit FenwickTree(const int n, const Abelian ID = 0); 要素数 $N$、単位元 $\mathrm{id}$ のオブジェクトを構築する。  
void add(int idx, const Abelian val); $A_{\mathrm{idx}} \gets A_{\mathrm{idx}} + \mathrm{val}$  
Abelian sum(int idx) const; $\sum_{i = 0}^{\mathrm{idx} - 1} A_i$  
Abelian sum(const int left, const int right) const; $\sum_{i = \mathrm{left}}^{\mathrm{right} - 1} A_i$  
Abelian operator[](const int idx) const; $A_{\mathrm{idx}}$  
int lower_bound(Abelian val) const; $\min \lbrace\,k \mid \sum_{i = 0}^k A_i \geq \mathrm{val} \rbrace$ $A_i \geq (\text{単位元})$ ($i = 0,\ldots, N - 1$)

区間加算クエリ対応 Fenwick tree

template <typename Abelian>
struct FenwickTreeSupportingRangeAddQuery;

メンバ関数

名前 効果・戻り値
explicit FenwickTreeSupportingRangeAddQuery(const int n_, const Abelian ID = 0); 要素数 $N$、単位元 $\mathrm{id}$ のオブジェクトを構築する。
void add(int left, const int right, const Abelian val); $A_i \gets A_i + \mathrm{val}$ ($i = \mathrm{left},\ldots, \mathrm{right} - 1$)
Abelian sum(const int idx) const; $\sum_{i = 0}^{\mathrm{idx} - 1} A_i$
Abelian sum(const int left, const int right) const; $\sum_{i = \mathrm{left}}^{\mathrm{right} - 1} A_i$
Abelian operator[](const int idx) const; $A_{\mathrm{idx}}$

2次元 Fenwick tree

template <typename Abelian>
struct FenwickTreeSupportingRangeAddQuery;

メンバ関数

名前 効果・戻り値
explicit FenwickTree2D(const int height_, const int width_, const Abelian ID = 0); 要素数 $\mathrm{height} \times \mathrm{width}$、単位元 $\mathrm{id}$ のオブジェクトを構築する。
void add(int y, int x, const Abelian val); $A_{yx} \gets A_{yx} + \mathrm{val}$
Abelian sum(int y, int x) const; $\sum_{i = 0}^y \sum_{j = 0}^x A_{ij}$
Abelian sum(const int y1, const int x1, const int y2, const int x2) const; $\sum_{i = y_1}^{y_2} \sum_{j = x_1}^{x_2} A_{ij}$
Abelian get(const int y, const int x) const; $A_{yx}$

区間加算クエリ対応2次元 Fenwick tree

template <typename Abelian>
struct FenwickTree2DSupportingRangeAddQuery;

メンバ関数

名前 効果・戻り値
explicit FenwickTree2DSupportingRangeAddQuery(const int height_, const int width_, const Abelian ID = 0); 要素数 $\mathrm{height} \times \mathrm{width}$、単位元 $\mathrm{id}$ のオブジェクトを構築する。
void add(int y1, int x1, int y2, int x2, const Abelian val); $A_{ij} \gets A_{ij} + \mathrm{val}$ ($y_1 \leq i \leq y_2,\ x_1 \leq j \leq x_2$)
Abelian sum(int y, int x) const; $\sum_{i = 0}^y \sum_{j = 0}^x A_{ij}$
Abelian sum(const int y1, const int x1, const int y2, const int x2) const; $\sum_{i = y_1}^{y_2} \sum_{j = x_1}^{x_2} A_{ij}$

区間加算クエリ対応2次元 Fenwick tree の実装

$A_{ij} \gets A_{ij} + v$ ($y_1 \leq i \leq y_2,\ x_1 \leq j \leq x_2$) を考える。

$S \mathrel{:=} \sum_{i = 1}^y \sum_{j = 1}^x A_{ij}$ とおき、加算前の $S$ を $S_b$、加算後の $S$ を $S_a$ とすると

参考文献

TODO

Submissons

Verified with

Code

#ifndef EMTHRM_DATA_STRUCTURE_FENWICK_TREE_FENWICK_TREE_SUPPORTING_RANGE_ADD_QUERY_HPP_
#define EMTHRM_DATA_STRUCTURE_FENWICK_TREE_FENWICK_TREE_SUPPORTING_RANGE_ADD_QUERY_HPP_

#include <vector>

namespace emthrm {

template <typename Abelian>
struct FenwickTreeSupportingRangeAddQuery {
  explicit FenwickTreeSupportingRangeAddQuery(
      const int n_, const Abelian ID = 0)
      : n(n_ + 1), ID(ID) {
    data_const.assign(n, ID);
    data_linear.assign(n, ID);
  }

  void add(int left, const int right, const Abelian val) {
    if (right < ++left) [[unlikely]] return;
    for (int i = left; i < n; i += i & -i) {
      data_const[i] -= val * (left - 1);
      data_linear[i] += val;
    }
    for (int i = right + 1; i < n; i += i & -i) {
      data_const[i] += val * right;
      data_linear[i] -= val;
    }
  }

  Abelian sum(const int idx) const {
    Abelian res = ID;
    for (int i = idx; i > 0; i -= i & -i) {
      res += data_linear[i];
    }
    res *= idx;
    for (int i = idx; i > 0; i -= i & -i) {
      res += data_const[i];
    }
    return res;
  }

  Abelian sum(const int left, const int right) const {
    return left < right ? sum(right) - sum(left) : ID;
  }

  Abelian operator[](const int idx) const { return sum(idx, idx + 1); }

 private:
  const int n;
  const Abelian ID;
  std::vector<Abelian> data_const, data_linear;
};

}  // namespace emthrm

#endif  // EMTHRM_DATA_STRUCTURE_FENWICK_TREE_FENWICK_TREE_SUPPORTING_RANGE_ADD_QUERY_HPP_
#line 1 "include/emthrm/data_structure/fenwick_tree/fenwick_tree_supporting_range_add_query.hpp"



#include <vector>

namespace emthrm {

template <typename Abelian>
struct FenwickTreeSupportingRangeAddQuery {
  explicit FenwickTreeSupportingRangeAddQuery(
      const int n_, const Abelian ID = 0)
      : n(n_ + 1), ID(ID) {
    data_const.assign(n, ID);
    data_linear.assign(n, ID);
  }

  void add(int left, const int right, const Abelian val) {
    if (right < ++left) [[unlikely]] return;
    for (int i = left; i < n; i += i & -i) {
      data_const[i] -= val * (left - 1);
      data_linear[i] += val;
    }
    for (int i = right + 1; i < n; i += i & -i) {
      data_const[i] += val * right;
      data_linear[i] -= val;
    }
  }

  Abelian sum(const int idx) const {
    Abelian res = ID;
    for (int i = idx; i > 0; i -= i & -i) {
      res += data_linear[i];
    }
    res *= idx;
    for (int i = idx; i > 0; i -= i & -i) {
      res += data_const[i];
    }
    return res;
  }

  Abelian sum(const int left, const int right) const {
    return left < right ? sum(right) - sum(left) : ID;
  }

  Abelian operator[](const int idx) const { return sum(idx, idx + 1); }

 private:
  const int n;
  const Abelian ID;
  std::vector<Abelian> data_const, data_linear;
};

}  // namespace emthrm
Back to top page