树状数组

树状数组, 可以高效地计算数列前缀和, 它的查询(求前缀和) 和更新(修改) 操作都可以在 O(logn) 的时间完成

tr[i] 存储以 i 为终点, 长度为 lowbit(i) 的区间

修改: for( int i = x ; i <= n ; i += lowbit(i) ) tr[i] += c

查询: for( int i = x ; i ; i -= lowbit(i) ) sum += tr[i]

//树状数组操作

//返回非负整数x在二进制表示下最低位1及其后面的0构成的数值
int lowbit (int x)
{
    return x&-x;
}

//将序列中第x个数加上k
void add (int x,int k)
{
    for(int i=x;i<=n;i+=lowbit(i))tr[i]+=k;
}

//查询序列前x个数的和
int ask (int x)
{
    int sum=0;
    for(int i=x;i;i-=lowbit(i))sum+=tr[i];
    return sum;
}

//O(n)的建树方法
void build ()
{
    for(int x=1;x<=n;x++)
    {
        tr[x]=a[x];
        for(int i=x-1;i>=x-lowbit(x)+1;i-=lowbit(i))
            tr[x]+=tr[i];
    }
}

树状数组的应用

① 点更新, 区间查询

② 区间更新, 点查询

使用差分, 维护差分数组 d[i] = a[i] - a[i-1]

区间更新变成了 [l,r] 两端 l 和 r 的更新, 点查询也就变成了 [1,x] 的区间查询

③ 区间更新, 区间查询

使用差分, 维护差分数组 c[i] = a[i] - a[i-1]

区间更新变成了 [l,r] 两端 l 和 r 的更新

对于求解一个 S = a[1,x] 的前缀和, 有:

S = a[1] + a[2] + \(\cdots\) + a[x]

\(\quad\) = c[1] + (c[1] + c[2]) + \(\cdots\) + (c[1] + c[2] + ... + c[x])

\(\quad\) = x*c[1] + (x-1)*c[2] + \(\cdots\) + 1*c[x]

\(\quad\) = (x+1) * (c[1] + c[2] + ... + c[x]) - (1*c[1] + 2*c[2] + ... + x*c[x])

因此可以使用另一个辅助数组 D 来维护 d[i] = i*c[i] 的前缀和

//区间更新,区间查询模板

int n;
int a[N],tr1[N],tr2[N];
//a[]存储原数组,b[i]=a[i]-a[i-1]为a的差分数组,tr1[i]维护b[i]的前缀和,tr2[i]维护i*b[i]的前缀和

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

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

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

int prefix_sum (int x)	//求a[1,x]的前缀和
{
    return sum(tr1,x)*(x+1)-sum(tr2,x);
}

int main()
{
    for(int i=1;i<=n;i++)
    {
        int b=a[i]-a[i-1];	//差分数组b[i]=a[i]-a[i-1]
        add(tr1,i,b);		//tr1[]维护b[i]的前缀和
        add(tr2,i,b*i);		//tr2[]维护i*b[i]的前缀和
    }
}