树状数组

class Sarr
{
public:
	Sarr()
	{
		memset(Bit, 0, sizeof(Bit));
	}
	int lowbit(int pos)
	{
		return pos & (-pos);
	}
	void update(int pos, int len)
	{
		while (pos <= len)
		{
			Bit[pos] += 1;
			pos += lowbit(pos);
		}
	}
	int getSum(int pos)
	{
		int sum = 0;
		while (pos)
		{
			sum += Bit[pos];
			pos -= lowbit(pos);
		}
		return sum;
	}
private:
	int Bit[100010];
}sarr;

原文：https://www.cnblogs.com/youseecode/p/14612346.html