欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

树状数组总结(单点修改 区间查询;区间修改 单点查询;区间修改 区间查询)

程序员文章站 2024-03-03 18:19:46
...

树状数组一般有三种题型吧

(1) 单点修改 区间查询

这应该是最简单的一个了,不多说了

#include<bits/stdc++.h>
using namespace std;
#define maxn 1100
#define lowbit(i) ((i)&(-i))
int n,c[maxn];
// 单点修改  区间查询
void update(int i,int val)
{
    while(i<=n){
        c[i]+=val;
        i+=lowbit(i);
    }
}
int sum(int i)
{
    int ans=0;
    while(i>0){
        ans+=c[i];
        i-=lowbit(i);
    }
    return ans;
}
int main()
{
    scanf("%d",&n);
    int x;
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        update(i,x);
    }
    int j,k,val;
    scanf("%d%d",&j,&val);   //修改j的值
    update(j,val);
    scanf("%d%d",&j,&k);   //查询(j,k)的值
    printf("%d\n",sum(k)-sum(j-1));
}

(2)区间修改 单点查询

这个我引用一下kanate_saikou的解释吧

这模板题名字就是树状数组..干嘛用线段树..代码还贼长..

这里介绍树状数组+差分思想,算是对下面大神的补充吧。

何为差分

现在我们有一个从小到大的数列a[]

a 1 3 6 8 9
然后还有一个差分数组b[]

b 1 2 3 2 1
相信某些小伙伴已经看出端倪了..这里b[i]=a[i]-a[i-1],我令a[0]=0,故b[1]=a[1]。

拥有了b数组,我们就可以很简单的求出bit[]中任意一个数,只需bit[i]=sigma(k=1 to i) b[k](这个很好推吧..)

我觉得现在该有人说我zz了..何必不直接查询a[i]而是找这么麻烦一个方法..这里我们转回正题!别忘了,题目要我们进行区间修改..

我们知道,树状数组对于单点值的修改十分方便(不懂的去看树状数组1),对于区间的修改就比较尴尬..而我们又不想敲死长的线段树..怎么办呢,这时候差分就显出优势

还是上面的a[]和b[],现在我们使区间[2,4]的所有数均+2,则a[]/b[]变为

a 1 5 8 10 9

b 1 4 3 2 -1
事实上,这里只有b[2]和b[5]发生了变化,因为区间内元素均增加了同一个值,所以b[3],b[4]是不会变化的。

这里我们就有了第二个式子:对于区间[x,y]的修改(增加值为d)在b数组内引起变化的只有 b[x]+=d,b[y+1]-=d。(这个也很好推的..)

这样,我们就把树状数组的软肋用差分解决了。
#include<bits/stdc++.h>
using namespace std;
#define maxn 1100
#define lowbit(i) ((i)&(-i))
int n,c[maxn];
// 区间修改  单点查询
void update(int i,int val)
{
    while(i<=n){
        c[i]+=val;
        i+=lowbit(i);
    }
}
int sum(int i)
{
    int ans=0;
    while(i>0){
        ans+=c[i];
        i-=lowbit(i);
    }
    return ans;
}
int main()
{
    scanf("%d",&n);
    int x=0;
    int y;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&y);
        update(i,y-x);         //这里就是区间修改的精髓了,那个差分数组b[]
        x=y;
    }
    int j,k,val;
    scanf("%d%d%d",&j,&k,&val);   //修改区间(j,k)的值
    update(j,val);
    update(k+1,-val);
    int p;
    scanf("%d",&p);    //查询
    printf("%d\n",sum(p));
}

(3)区间修改 区间查询

现在有一个原数组a,有一个数组d,d[i] = a[i] - a[i-1],那么 a[i] = d[1] + d[2] + .... + d[i],

d数组就是差分数组

所以求a[i]就可以用树状数组维护d[i]的前缀和;

所以可以得到:

a[1] + a[2] + a[3] + ... + a[k] = d[1] + d[1] + d[2] + d[1] + d[2] + d[3] + ... + d[1] + d[2] + d[3] + ... + d[k]

= Σ(k - i + 1) * d[i]  (i从1到k)

变化一下 Σa[i] (i从1到k) = Σ(k+1) * d[i] - i * d[i] (i从1到k)

d[i]可以用一个前缀和维护,i * d[i]也可以用一个前缀和进行维护,所以区间修改,区间查询就变得很方便了

假设c维护d[i]的前缀和,c2维护d[i] * i的前缀和

#include<bits/stdc++.h>
using namespace std;
#define maxn 1100
#define lowbit(i) ((i)&(-i))
int n,c[maxn],c2[maxn];
void update (int p,int val)    //区间更新
{
    for(int i=p;i<=n;i+=lowbit(i)){
        c[i]+=val;
        c2[i]+=p*val;
    }
}
int sum(int p)    //前p项和
{
    int ans1;
    int ans2;
    for(int i=p;i>0;i-=lowbit(i)){
        ans1+=(p+1)*c[i];
        ans2+=c2[i];
    }
    return ans2-ans1;
}
int main()
{
    scanf("%d",&n);
    int x=0,y;
    for(int i=1;i<=n;i++){
        scanf("%d",&y);
        update(i,y-x);     //仍然是区间修改,还需要差分
        x=y;
    }
    int j,k,val;
    scanf("%d%d%d",&j,&k,&val);     //修改(j,k)区间
    update(j,val);
    update(k+1,-val);
    scanf("%d%d",&j,&k);
    printf("%d\n",sum(j)-sum(k-1));
}