binary-indexed-tree
(kyopro/library/datastructure/BIT.cpp)

• View this file on GitHub
• Last update: 2022-07-20 00:04:43+09:00



概要

ある列の区間の和と一点更新が高速にできる
一応抽象化をしているが二項演算は $+$ と $-$ のままなので実質数列限定
変なのを乗せるときは segment tree をつかう

使い方

構造体

宣言

BIT<$T$> bit($n$);
$T$: 型
$n$: 大きさ

一点更新

bit.add($i, a$)

• $i$: 追加する index
• $a$: 足す値

区間取得

bit.sum($l, r$)

• $l, r$: 区間 $[l, r)$ の和を取得する。

計算量

• 一点更新・区間取得
  ${\rm O}(n \log n)$

Verified with

• kyopro/test/BIT_yosupo-judge.test.cpp
• kyopro/test/mo_yosupo-judge.test.cpp

Code

/*
* @title binary-indexed-tree
* @docs kyopro/docs/BIT.md
*/

template<typename T>
//0-indexed/内部的に 1-indexed
struct BIT {
	vector<T> tree;
	//初期化
	BIT(int n) : tree(n) {
		tree.assign(n + 1, 0);
	}

	int LSB(int n) { return (n & (-n)); }

	//[0, n) の sum を返す/0-indexed
	T sum(int n) {
		T ret = 0;
		//実は 1-indexed だが半開区間なので見た目がそのまま
		for (; n >= 0; n -= LSB(n)) {
			ret += tree[n];
			if (!n)break;
		}
		return ret;
	}


	//[i, j) の sum を返す/0-indexed
	T sum(int i, int j) {
		return sum(j) - sum(i);
	}

	//n 番目に x を足す
	void add(int n, T x) {
		int siz = tree.size();
		for (++n; n < siz; n += LSB(n))tree[n] += x;
	}
};

#line 1 "kyopro/library/datastructure/BIT.cpp"
/*
* @title binary-indexed-tree
* @docs kyopro/docs/BIT.md
*/

template<typename T>
//0-indexed/内部的に 1-indexed
struct BIT {
	vector<T> tree;
	//初期化
	BIT(int n) : tree(n) {
		tree.assign(n + 1, 0);
	}

	int LSB(int n) { return (n & (-n)); }

	//[0, n) の sum を返す/0-indexed
	T sum(int n) {
		T ret = 0;
		//実は 1-indexed だが半開区間なので見た目がそのまま
		for (; n >= 0; n -= LSB(n)) {
			ret += tree[n];
			if (!n)break;
		}
		return ret;
	}


	//[i, j) の sum を返す/0-indexed
	T sum(int i, int j) {
		return sum(j) - sum(i);
	}

	//n 番目に x を足す
	void add(int n, T x) {
		int siz = tree.size();
		for (++n; n < siz; n += LSB(n))tree[n] += x;
	}
};

Back to top page