区間加算 Binary Indexed Tree
(DataStructure/BinaryIndexedTree_RangeAdd.hpp)

• View this file on GitHub
• Last update: 2021-03-18 15:32:11+09:00
• Include: #include "DataStructure/BinaryIndexedTree_RangeAdd.hpp"
• Link: https://tkmst201.github.io/Library/DataStructure/BinaryIndexedTree_RangeAdd.hpp

概要

Binary Indexed Tree を用いた配列の区間和を扱うデータ構造です。
要素数 $N$ の配列に対し、区間一樣加算や任意の区間和の計算を $\Theta(\log{N})$ で行うことができます。
遅延セグメント木 に比べ、より省メモリで定数倍が良いです。

• BinaryIndexedTree(size_t n)
  • $\Theta(n)$ 要素数 $n$ で初期化
• size_t size()
  • $\Theta(1)$ 配列の要素数 $N$ を返す
• void add(size_t l, size_t r, T x)
  • $\mathcal{O}(\log{N})$ 区間 $[l, r)$ に $x$ を一様加算する
• T sum(size_t i)
  • $\mathcal{O}(\log{N})$ $\sum_{k=0}^{i-1} A_k$ を返す
• T sum(size_t l, size_t r)
  • $\mathcal{O}(\log{N})$ $\sum_{k=l}^{r-1} A_k$ を返す

コンストラクタ

制約

• T は int, long long, ModInt

---

BinaryIndexedTree_RagneAdd(size_t n)

要素数 $n$ で初期化します。 初期値は $0$ です。

計算量

• $\Theta(n)$

---

メンバ関数

以下、要素数 $N$ の配列 $A_0, A_1, \ldots, A_{N-1}$ を対象とします。

---

size_t size()

配列の要素数 $N$ を返します。

計算量

• $\Theta(1)$

---

void add(size_t l, size_t r, T x)

$i = l, l+1, \ldots, r-1$ に対して $A_i$ += $x$ をします。 $l = r$ のときは何も行いません。

制約

• $0 \leq l \leq r \leq N$

計算量

• $\mathcal{O}(\log{N})$

---

T sum(size_t i)

$\sum_{k=0}^{i-1} A_k$ を返します。 $i = 0$ のときは $0$ を返します。

制約

• $0 \leq i \leq N$

計算量

• $\mathcal{O}(\log{N})$

---

T sum(size_t l, szie_t r)

$\sum_{k=l}^{r-1} A_k$ を返します。 $l = r$ のときは $0$ を返します。

制約

• $0 \leq l \leq r \leq N$

計算量

• $\mathcal{O}(\log{N})$

---

使用例

オーバーフローに注意してください。総和が $2^{31}$ 以上になる場合は long long を使いましょう。

#include <bits/stdc++.h>
#include "DataStructure/BinaryIndexedTree_RangeAdd.hpp"
using namespace std;

int main() {
	BinaryIndexedTree_RangeAdd<int> bit(5);
	cout << "N = " << bit.size() << endl; // 5
	
	bit.add(1, 3, 2);
	// 0 2 2 0 0
	for (int i = 0; i < bit.size(); ++i) cout << bit.sum(i, i + 1) << " \n"[i + 1 == bit.size()];
	
	bit.add(0, 2, -1);
	// -1 1 2 0 0
	for (int i = 0; i < bit.size(); ++i) cout << bit.sum(i, i + 1) << " \n"[i + 1 == bit.size()];
	
	cout << "sum = " << bit.sum(bit.size()) << endl; // 2
}

参考

2020/08/15: https://algo-logic.info/binary-indexed-tree/

Depends on

• Binary Indexed Tree (DataStructure/BinaryIndexedTree.hpp)

Verified with

• Test/BinaryIndexedTree_RangeAdd.test.cpp

Code

#ifndef INCLUDE_GUARD_BINARY_INDEXED_TREE_RANGE_ADD_HPP
#define INCLUDE_GUARD_BINARY_INDEXED_TREE_RANGE_ADD_HPP

#include "DataStructure/BinaryIndexedTree.hpp"

#include <vector>
#include <cassert>

/**
 * @brief https://tkmst201.github.io/Library/DataStructure/BinaryIndexedTree_RangeAdd.hpp
 */
template<typename T>
struct BinaryIndexedTree_RangeAdd {
	static_assert(std::is_integral<T>::value == true);
	
	using bit_type = BinaryIndexedTree<T>;
	using value_type = typename bit_type::value_type;
	using size_type = typename bit_type::size_type;
	
private:
	std::vector<bit_type> bit;
	
public:
	explicit BinaryIndexedTree_RangeAdd(size_type n)
		: bit(2, bit_type{n, 0, [](value_type x, value_type y) { return x + y; }}) {}
	
	size_type size() const noexcept {
		return bit[0].size();
	}
	
	void add(size_type l, size_type r, value_type x) noexcept {
		assert(l <= r);
		assert(r <= size());
		if (l == r) return;
		bit[0].add(l, x);
		bit[0].add(r - 1, -x);
		bit[1].add(l, -x * l);
		bit[1].add(r - 1, x * r);
	}
	
	value_type sum(size_type i) noexcept {
		assert(i <= size());
		return bit[0].sum(i) * i + bit[1].sum(i);
	}
	
	value_type sum(size_type l, size_type r) noexcept {
		assert(l <= r);
		assert(r <= size());
		if (l == r) return 0;
		return sum(r) - sum(l);
	}
};

#endif // INCLUDE_GUARD_BINARY_INDEXED_TREE_RANGE_ADD_HPP

#line 1 "DataStructure/BinaryIndexedTree_RangeAdd.hpp"



#line 1 "DataStructure/BinaryIndexedTree.hpp"



#include <vector>
#include <cassert>
#include <functional>

/**
 * @brief https://tkmst201.github.io/Library/DataStructure/BinaryIndexedTree.hpp
 */
template<typename T>
struct BinaryIndexedTree {
	using value_type = T;
	using const_reference = const value_type &;
	using F = std::function<value_type (const_reference, const_reference)>;
	using size_type = std::size_t;
	
private:
	size_type n;
	value_type id_elem;
	F f;
	std::vector<value_type> node;
	
public:
	BinaryIndexedTree(size_type n, const_reference id_elem, const F & f)
		: n(n), id_elem(id_elem), f(f), node(n + 1, id_elem) {}
	
	size_type size() const noexcept {
		return n;
	}
	
	void add(size_type i, const_reference x) noexcept {
		assert(i < size());
		++i;
		for (; i <= size(); i += i & -i) node[i] = f(node[i], x);
	}
	
	value_type sum(size_type i) const noexcept {
		assert(i <= size());
		value_type res = id_elem;
		for (; i > 0; i -= i & -i) res = f(node[i], res);
		return res;
	}
	
	size_type lower_bound(const_reference x) const noexcept {
		size_type res = 0;
		size_type s = id_elem, w = 1;
		while (w < size()) w <<= 1;
		for (; w > 0; w >>= 1) {
			if (res + w <= size()) {
				value_type cur = f(s, node[res + w]);
				if (cur < x) {
					res += w;
					s = cur;
				}
			}
		}
		return res;
	}
};


#line 5 "DataStructure/BinaryIndexedTree_RangeAdd.hpp"

#line 8 "DataStructure/BinaryIndexedTree_RangeAdd.hpp"

/**
 * @brief https://tkmst201.github.io/Library/DataStructure/BinaryIndexedTree_RangeAdd.hpp
 */
template<typename T>
struct BinaryIndexedTree_RangeAdd {
	static_assert(std::is_integral<T>::value == true);
	
	using bit_type = BinaryIndexedTree<T>;
	using value_type = typename bit_type::value_type;
	using size_type = typename bit_type::size_type;
	
private:
	std::vector<bit_type> bit;
	
public:
	explicit BinaryIndexedTree_RangeAdd(size_type n)
		: bit(2, bit_type{n, 0, [](value_type x, value_type y) { return x + y; }}) {}
	
	size_type size() const noexcept {
		return bit[0].size();
	}
	
	void add(size_type l, size_type r, value_type x) noexcept {
		assert(l <= r);
		assert(r <= size());
		if (l == r) return;
		bit[0].add(l, x);
		bit[0].add(r - 1, -x);
		bit[1].add(l, -x * l);
		bit[1].add(r - 1, x * r);
	}
	
	value_type sum(size_type i) noexcept {
		assert(i <= size());
		return bit[0].sum(i) * i + bit[1].sum(i);
	}
	
	value_type sum(size_type l, size_type r) noexcept {
		assert(l <= r);
		assert(r <= size());
		if (l == r) return 0;
		return sum(r) - sum(l);
	}
};

Back to top page