binary_indexed_tree(BIT) (tree/binary_indexed_tree.cpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-10-25 02:18:11+09:00

なにこれ

一点加算・区間和取得を対数時間で行うことができるデータ構造． セグメント木より定数倍が軽い．

コンストラクタ

• BIT(n)：要素数 n の BIT を構築する．
• BIT(v)：配列 v の要素で BIT を構築する．

メンバ関数

• sum(idx)：$[1, \mathrm{idx}]$ の要素の総和を返す．
• sum(l, r)：$[l, r]$ の要素の総和を返す．
• get(idx)：$\mathrm{idx}$ 番目の要素の値を返す．
• add(idx, val)：$\mathrm{idx}$ 番目の要素に val を加える．

idx, l, r は 1-indexed である．

計算量

• BIT(n)：$O(n)$
• BIT(v)：$O(n)$
• sum(idx)：$O(\log n)$
• sum(l, r)：$O(\log n)$
• get(idx)：$O(\log n)$
• add(idx, val)：$O(\log n)$

Required by

• Inversion-Number(転倒数) (math/inversion_number.cpp)

Verified with

• test/aoj_ALDS1_5_D.cpp
• test/yosupo_static_range_sum_BIT.cpp

Code

#pragma once

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

template<typename T> struct BIT {
private:
	vector<T> node;
	const int N;

public:
	BIT(int n) : node(n + 1, 0), N(n) {}
	BIT(const vector<T> &v) : node(v.size() + 1, 0), N(v.size()) {
		for(int i = 0; i < N; i++) node[i + 1] = v[i];
		for(int i = 1; i < N; i++) {
			int j = i + (i & -i);
			if(j <= N) node[j] += node[i];
		}
	}

	T sum(int idx) {
		assert(0 <= idx && idx <= N);
		T res = 0;
		while(idx) {
			res += node[idx];
			idx -= idx & -idx;
		}
		return res;
	}

	T sum(int l, int r) {
		assert(0 <= l && r <= N);
		if(l > r) return T(0);
		return sum(r) - sum(max(l - 1, 0));
	}

	inline T get(int idx) {
		assert(0 < idx and idx <= N);
		return sum(idx, idx);
	}

	void add(int idx, T val) {
		assert(0 < idx && idx <= N);
		while(idx <= N) {
			node[idx] += val;
			idx += idx & -idx;
		}
	}
};

#line 2 "tree/binary_indexed_tree.cpp"

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

template<typename T> struct BIT {
private:
	vector<T> node;
	const int N;

public:
	BIT(int n) : node(n + 1, 0), N(n) {}
	BIT(const vector<T> &v) : node(v.size() + 1, 0), N(v.size()) {
		for(int i = 0; i < N; i++) node[i + 1] = v[i];
		for(int i = 1; i < N; i++) {
			int j = i + (i & -i);
			if(j <= N) node[j] += node[i];
		}
	}

	T sum(int idx) {
		assert(0 <= idx && idx <= N);
		T res = 0;
		while(idx) {
			res += node[idx];
			idx -= idx & -idx;
		}
		return res;
	}

	T sum(int l, int r) {
		assert(0 <= l && r <= N);
		if(l > r) return T(0);
		return sum(r) - sum(max(l - 1, 0));
	}

	inline T get(int idx) {
		assert(0 < idx and idx <= N);
		return sum(idx, idx);
	}

	void add(int idx, T val) {
		assert(0 < idx && idx <= N);
		while(idx <= N) {
			node[idx] += val;
			idx += idx & -idx;
		}
	}
};

Back to top page