class TreeArray
{
int c[1100000]; // element id must start at 1
int size;
int lowbit(int x)
{
return x & (-x);
}
public:
void init(int s = N - 1)
{
size = s;
memset(c,0,size * sizeof(c[0]));
}
int sum(int n) // 前n个数的和，包括n
{
int s = 0;
while (n > 0)
{
s += c[n];
n -= lowbit(n);
}
return s;
}
void plus(int p,int x) // add x to the element at position p
{
while (p <= size)
{
c[p] += x;
p += lowbit(p);
}
}
};