fenwick_tree (一点加算、区間和取得)
(src/dataStructure/fenwick_tree.hpp)

• View this file on GitHub
• Last update: 2023-01-29 05:23:46+09:00
• Include: #include "src/dataStructure/fenwick_tree.hpp"

概要

フェニック木 です。

集合と演算の組 $(S, \oplus)$ について

• 結合則
• 交換則
• 単位元の存在
• 逆元の存在

を満たす時、$x\ \in S$ からなる列 $A$ に対して以下のクエリに答えることができます。

• $A_i\ \leftarrow\ A_i\ \oplus\ x$
• $\displaystyle \bigoplus_{i = l}^{r - 1} A_i$ を求める

機能

コンストラクタ

zawa::fenwick_tree<structure> fen(std::size_t n)

• $A$ を 長さ $n$ の各要素を structure::id で初期化する
• structure
  • 以下の要素を持つ構造体
  • typename T: 型
  • static constexpr T id: 単位元
  • static T add(const T& a, const t& b): 演算
  • static T inverse(const T& a): 逆元を返す
  • 例はsrc/utility/fenwick_treeを確認ください
• 計算量 : $O(n)$

zawa::fenwick_tree<structure> fen(const std::vector<structure::T>& A)

• $A$ をAで初期化する
• 計算量 : $O(\mid A\mid \log \mid A \mid)$

メンバ関数

void add(int pos, const T& v)

• $A_{\text{pos}}\ \leftarrow\ A_{\text{pos}}\ \oplus v$ とする
• 制約: $0\ \le\ \text{pos}\ <\ n$
• 計算量 : $O(\log n)$

T sum(int l, int r)

• $\displaystyle \bigoplus_{i = l}^{r - 1} A_i$ を求めます
• 制約: $0\ \le\ l\ \le\ r\ \le\ n$
• 計算量 : $O(\log n)$

int lower_bound(T val)

• sum(0, r) >= val を満たす最小のrを返します。
• 計算量 : $O(\log n)$

Required by

• fenwick_multiset (動的多重集合) (src/dataStructure/fenwick_multiset.hpp)
• fenwick_set (動的集合) (src/dataStructure/fenwick_set.hpp)

Verified with

• test/ABC185-E.test.cpp
• test/ABC186-F.test.cpp
• test/ARC033-C.test.cpp
• test/ARC075-E.test.cpp
• test/fenwick_tree.test.cpp
• test/fenwick_tree2.test.cpp

Code

#pragma once

#include <vector>

namespace zawa {

template <class structure>
class fenwick_tree {
private:
	using T = typename structure::T;
	std::vector<T> dat;
	int pow_two;

	inline int lsb(int x) {
		return x & -x;
	}

	T sum(int r) {
		T res = 0;
		while (r > 0) {
			res = structure::add(res, dat[r]);
			r -= lsb(r);
		}
		return res;
	}
	
public:

	fenwick_tree(std::size_t n) : dat(n + 1, structure::id), pow_two(std::__lg(n) + 1) {}
	
	fenwick_tree(const std::vector<T>& A) : dat(A.size() + 1, structure::id), pow_two(std::__lg(A.size()) + 1) {
		for (int i = 0 ; i < (int)A.size() ; i++) {
			add(i, A[i]);
		}
	}


	T sum(int l, int r) {
		return structure::add(sum(r), structure::inverse(sum(l)));
	}

	void add(int pos, const T& v) {
		pos++;
		while (pos < (int)dat.size()) {
			dat[pos] = structure::add(dat[pos], v);
			pos += lsb(pos);
		}
	}

	int lower_bound(T val) {
		int res = 0;
		T now = structure::id;
		for (int x = (1 << pow_two) ; x > 0 ; x >>= 1) {
			if (res + x < (int)dat.size()) {
				T nxt = structure::add(now, dat[res + x]);
				if (nxt < val) {
					res += x;
					now = nxt;
				}
			}
		}
		return res;
	}
};

} // namespace zawa

#line 2 "src/dataStructure/fenwick_tree.hpp"

#include <vector>

namespace zawa {

template <class structure>
class fenwick_tree {
private:
	using T = typename structure::T;
	std::vector<T> dat;
	int pow_two;

	inline int lsb(int x) {
		return x & -x;
	}

	T sum(int r) {
		T res = 0;
		while (r > 0) {
			res = structure::add(res, dat[r]);
			r -= lsb(r);
		}
		return res;
	}
	
public:

	fenwick_tree(std::size_t n) : dat(n + 1, structure::id), pow_two(std::__lg(n) + 1) {}
	
	fenwick_tree(const std::vector<T>& A) : dat(A.size() + 1, structure::id), pow_two(std::__lg(A.size()) + 1) {
		for (int i = 0 ; i < (int)A.size() ; i++) {
			add(i, A[i]);
		}
	}


	T sum(int l, int r) {
		return structure::add(sum(r), structure::inverse(sum(l)));
	}

	void add(int pos, const T& v) {
		pos++;
		while (pos < (int)dat.size()) {
			dat[pos] = structure::add(dat[pos], v);
			pos += lsb(pos);
		}
	}

	int lower_bound(T val) {
		int res = 0;
		T now = structure::id;
		for (int x = (1 << pow_two) ; x > 0 ; x >>= 1) {
			if (res + x < (int)dat.size()) {
				T nxt = structure::add(now, dat[res + x]);
				if (nxt < val) {
					res += x;
					now = nxt;
				}
			}
		}
		return res;
	}
};

} // namespace zawa

Back to top page