树状数组初步
发布时间:2020-12-14 03:48:15 所属栏目:大数据 来源:网络整理
导读:树状数组 FUCTION: (begin{cases}text{点单修改区间求和} text{区间修改单点查询} text{区间修改区间查询}end{cases}) 原理:定义c[i],表示以i为结尾的前lowbit(i)个数(原数列)的和(后缀和) 维护c[i],根据上图,从底至上(二进制增加拼凑)更新code
树状数组FUCTION:(begin{cases}text{点单修改&&区间求和} text{区间修改&&单点查询} text{区间修改&&区间查询}end{cases}) 原理:定义c[i],表示以i为结尾的前lowbit(i)个数(原数列)的和(后缀和)维护c[i],根据上图,从底至上(二进制增加拼凑)更新code:inline void update(int pos,int val){ for(int i=pos;i<=n;i+=lowbit(i))c[i]+=val; } APP1:单点修改&&区间查询区间查询:前缀和的思想,query(l,r)=sum(r)-sum(l-1)code:query(实质是根据上图的自顶向底(二进制拆分)) inline void query(int pos){ int ans=0; for(int i=pos;i;i-=lowbit(i))ans+=c[i]; return ans; }//调用query(r)-query(l-1) APP2:区间修改&&单点查询solution:维护差分数组d[i],根据d数组维护c[i],区间修改转化成单点修改(在端点处修改),单点查询转化成区间求和(差分数组的前缀和)code: update(l,val); update(r+1,-val);//[l,r]+val query(pos)//单点查询 APP3:区间修改&&区间查询(sumlimits_{i=1}^pa_i=sumlimits_{i=1}^psumlimits_{j=1}^i d[j]=sumlimits_{i=1}^p(p+i-1)d[i]=(p+1)sumlimits_{i=1}^pd[i]-sumlimits_{i=1}^p d[i]times i) #include<cstdio> #include<cstring> #include<iostream> using namespace std; const int MAXX=101000; long long a[MAXX],d[MAXX],c[MAXX],ci[MAXX],di[MAXX]; int n,q; inline long long lowbit(long long x){ return x&-x; } inline void add(long long pos,long long val){ for(long long i=pos;i<=n;i+=lowbit(i)){ c[i]+=val; ci[i]+=val*pos; } } inline void update(long long l,long long r,long long val){ add(l,val); add(r+1,-val); } inline long long query(long long pos){ long long ans1=0; long long ans2=0; for(long long i=pos;i;i-=lowbit(i)){ ans1+=c[i]; ans2+=ci[i]; } return ans1*(pos+1)-ans2; } int main(){ scanf("%d%d",&n,&q); for(long long i=1;i<=n;++i){ scanf("%lld",&a[i]); add(i,a[i]-a[i-1]); } for(long long i=1;i<=q;++i){ int opt,l,r; long long val; scanf("%d%d%d",&opt,&l,&r); if(opt==1){ scanf("%lld",&val); update(l,r,val); } else printf("%lldn",query(r)-query(l-1)); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |