ACM模版
一维
#define typev int // type of res
const int N = 1010;
typev ar[N];
int lowb(int t)
{
return t & (-t);
}
void add(int i, typev v)
{
for (; i < N; ar[i] += v, i += lowb(i));
return ;
}
typev sum(int i)
{
typev s = 0;
for (; i > 0; s += ar[i], i -= lowb(i));
return s;
}
二维
const int N = 10000;
int c[N][N];
int Row, Col;
inline int Lowbit(const int &x)
{
return x & (-x);
}
int Sum(int i, int j)
{
int tempj, sum = 0;
while (i > 0)
{
tempj = j;
while (tempj > 0)
{
sum += c[i][tempj];
tempj -= Lowbit(tempj);
}
i -= Lowbit(i);
}
return sum;
}
void Update(int i, int j, int num)
{
int tempj;
while (i <= Row)
{
tempj = j;
while (tempj <= Col)
{
c[i][tempj] += num;
tempj += Lowbit(tempj);
}
i += Lowbit(i);
}
return ;
}