BIT.cpp

struct BIT{
	int N;
	vector<int> bit;
	void init(int n)
	{
		N = n;
		bit.assign(n + 1, 0);
	}
	void update(int idx, int val)
	{
		while(idx <= N)
		{
			bit[idx] += val;
			idx += idx & -idx;
		}
	}
	void updateMax(int idx, int val)
	{
		while(idx <= N)
		{	bit[idx] = max(bit[idx], val);
			idx += idx & -idx;
		}
	}
	int pref(int idx)
	{
		int ans = 0;
		while(idx > 0)
		{	ans += bit[idx];
			idx -= idx & -idx;
		}
		return ans;
	}
	int rsum(int l, int r)
	{
		return pref(r) - pref(l - 1);
	}
	int prefMax(int idx)
	{	int ans = -2e9;
		while(idx > 0)
		{
			ans = max(ans, bit[idx]);
			idx -= idx & -idx;
		}
		return ans;
	}
};
/*
BIT b;
b.init(10);
*/