运用范围

题目可以转化为 修改某一个数 + 求前缀和

基本操作

 int lowbit(int x)
{
    return x & -x;
}

修改

void add(int x, int c)
{
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

查询

int sum(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

初始化

//O(nlogn)
int tr[N], a[N];
for (int i = 1; i <= n; i ++ ) add(i, a[i]);

//O(2n-1) 一般用不到
//x用x的儿子来初始化,tr[x] = tr[x - 1] + a[x];
for (int i = 1; i <= n; i ++ ) tr[i] = a[i];
for (int x = 1;x <= n;x ++)
    for (int i = x - 1; i >= x - lowbit(x) + 1; i -= lowbit(i))
         tr[x] += tr[i];

//O(n) 一般用不到 不确定是不是这么写
//tr[x] = a[x - lowbit + 1 ~ x] = s[x] - s[x - lowbit(x)];
for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i];
for (int x = 1; x <= n; x ++)
    for (int i = x - 1; i >= x - lowbit(x) + 1; i -= lowbit(i))
         tr[x] = s[x] - s[x - lowbit(x)];