---
tags: codebook
---

{%hackmd theme-dark %}

# BIT(Binary Index Tree)

#include<vector>
using namespace std;
template<typename T>
struct BIT {
	size_t size;
	vector<T> data;
	BIT(size_t s): size(s), data(size + 1, 0) {}
	inline void update(int i, int x) {
		i++;
		auto lowbit = [](auto x) {return x & -x;};
		while (i <= int(size))
			data[i] += x, i += lowbit(i);
	}
	inline int query(int i) {
		i++;
		int res = 0;
		auto lowbit = [](auto x) {return x & -x;};
		while (i > 0)
			res += data[i], i -= lowbit(i);
		return res;
	}
};