BIT

bit.cpp

#include <vector>

class BIT {
private:
	vector<int> ft;
	int size;

	int lastone(int S) {
		return S & (-S);
	}

public:
	BIT(int n) : ft(n), size(n) {}

	int sum(int b) {
		int sum = 0;
		for (; b; b -= lastone(b)) sum += ft[b];
		return sum;
	}

	int sum(int a, int b) {
		return sum(b) - (a == 1 ? 0 : sum(a - 1));
	}

	void update(int k, int v) {
		for (; k <= size; k += lastone(k)) ft[k] += v;
	}
};