poj 3468 题意就是区间修改和区间求和。
开始没考虑如对1-10这个区间只更新了1-5，求和1-10的时候没加这个更新，应该结构上加上个b。
#include<iostream> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <map> #include <set> #include <algorithm> using namespace std; const int maxn=100000+7; struct ttt{ long long l,r,w,a,b; }; long long qq[maxn]; ttt tree[4*maxn]; int build(long long l,long long r,int num){ tree[num].l=l; tree[num].r=r; if(l==r){ tree[num].w=qq[l];return 0; } build(l,(l+r)/2,num+num); build((l+r)/2+1,r,num+num+1); tree[num].w=tree[num+num].w+tree[num+num+1].w; } int update(long long l,long long r,long long y,int num){ if(tree[num].l>=l&&tree[num].r<=r){ //区间属于l,r tree[num].a+=y; return 0; } tree[num].b+=y*(min(r,tree[num].r)-max(l,tree[num].l)+1);//考虑这个区间只加部分，但是选这个区间 //得考虑这部分和也得选上 int mid1=(tree[num].l+tree[num].r)/2; if(l>mid1){ update(l,r,y,num+num+1); }else if(r<=mid1){ update(l,r,y,num+num); }else if(l<=mid1&&r>mid1){ update(l,r,y,num+num); update(l,r,y,num+num+1); } } long long sum1; int find1(long long l,long long r,int num){ if(l<=tree[num].l&&r>=tree[num].r){ //区间属于l,r sum1+=tree[num].w+tree[num].a*(tree[num].r-tree[num].l+1); sum1+=tree[num].b; }else{ sum1+=tree[num].a*(min(r,tree[num].r)-max(l,tree[num].l)+1); //l,r在这个区间的值 int mid1=(tree[num].l+tree[num].r)/2; if(l>mid1){ find1(l,r,num+num+1); }else if(r<=mid1){ find1(l,r,num+num); }else if(l<=mid1&&r>mid1){ find1(l,r,num+num); find1(l,r,num+num+1); } } } int main(){ long long i,j,k,f1,f2,f3,f4,t1,t2,t3,t4,n,m; //reopen("in.txt","r",stdin); memset(tree,0,sizeof(tree)); cin >> n >> m; t3=0; for(i=1;i<=n;i++){ scanf("%lld",&qq[i]); } scanf("\n"); char b; build(1,n,1); for(i=1;i<=m;i++){ scanf("%c %lld %lld",&b,&t1,&t2); if(b=='Q'){ scanf("\n"); sum1=0; find1(t1,t2,1); printf("%lld\n",sum1); }else{ scanf("%lld\n",&t3); update(t1,t2,t3,1); } } return 0; }树状数组也能区间更新和查找，速度会更快一些，开的数组就是n的大小。
#include <iostream> #include <stdio.h> #include <string.h> #include <stack> #include <vector> #include <algorithm> #include <set> using namespace std; const int maxn=1e6+7; typedef long long ll; ll n,c1[maxn],c2[maxn]; ll lowbits(ll x){ return x&(-x);} void add(ll *r,ll pos,ll v){ while(pos<=n){ r[pos]+=v; pos+=lowbits(pos); } } ll sigma(ll *r,ll pos){ ll anx=0; while(pos>0){ anx+=r[pos]; pos-=lowbits(pos); } return anx; } int main(){ //freopen("in.txt","r",stdin); long long i,j,k,f1,f2,f3,t1,t2,t3,sum1,sum2; int m; cin >> n>>m; for(i=1;i<=n;i++){ scanf("%lld",&f3); f1=f2=i; add(c1,f1,f3);add(c1,f2+1,-f3); add(c2,f1,f3*(f1-1));add(c2,f2+1,-f3*f2); } char b; scanf("\n"); while(m--){ scanf("%c %lld %lld",&b,&f1,&f2); if(b=='C'){ //t2==1时候,f1-f2加f3 scanf("%lld\n",&f3); add(c1,f1,f3);add(c1,f2+1,-f3); add(c2,f1,f3*(f1-1));add(c2,f2+1,-f3*f2); }else{ //t2==2 的时候 查询f1-f2的和 scanf("\n"); sum1=(f1-1)*sigma(c1,f1-1)-sigma(c2,f1-1); sum2=f2*sigma(c1,f2)-sigma(c2,f2); cout << sum2-sum1 << endl; } } return 0; }
