Fenwick木

目的

長さ$n$の数列に対して、a[k]にある数を加算・範囲和$\sum_{l\le i \lt r}a[i]$を計算の二つのクエリを$O(\log n)$で計算するデータ構造。

計算量

$O(n\log n)$

使い方

class BIT
Fenwick木の構造体
int[] a
数列a
int n
数列aの長さ
void add(int k,int add)
a[k]にaddを加算
int sum(int k)
$\sum_{0\le i \lt k}a[i]$をreturn
int sum(int a,int b)
$\sum_{a\le i \lt b}a[i]$をreturn

ソースコード

class BIT {
	int n;
	int[] a;

	public BIT(int n_) {
		n = n_;
		a = new int[n + 1];
	}

	void add(int k, int add) {
		++k;
		while (k < a.length) {
			a[k] += add;
			k += k & -k;
		}
	}

	int sum(int k) {
		++k;
		int ret = 0;
		while (k > 0) {
			ret += a[k];
			k -= k & -k;
		}
		return ret;
	}

	int sum(int a, int b) {
		return sum(b - 1) - sum(a - 1);
	}
}