题目链接：传送门
题目大意：略
题目思路：线段树or树状数组
我们可以将区间值做一些调整。a*3+b*2+c=a+(a+b)+(a+b+c)
也就是利用前缀和建树。然后单点更新也就转换成了区间更新。修改一个点x时，需要修改 x~n 的值（因为是按前缀和建树
查询时也很简单，查询 x~y，则直接返回 x~y的值，再减去 （x-1的值）*（y-x+1），要把（1~x）的前缀和减去。
用线段树时要注意一个坑点，若查询时 x==1，则不用减去任何值直接输出即可，否则有可能RE（别问我怎么知道的
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <cstring> #include <stack> #include <cctype> #include <queue> #include <string> #include <vector> #include <set> #include <map> #include <climits> #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r ///宏 #define fi first #define se second #define ping(x,y) ((x-y)*(x-y)) #define mst(x,y) memset(x,y,sizeof(x)) #define mcp(x,y) memcpy(x,y,sizeof(y)) using namespace std; #define gamma 0.5772156649015328606065120 #define MOD 1000000007 #define inf 0x3f3f3f3f #define N 1000005 #define maxn 100005 typedef pair<int,int> PII; typedef long long LL; int n,m,k,cnt,L,R; LL a[maxn],mrk[maxn<<2],v; struct Node{ int l,r; LL v; }node[maxn<<2]; void build(int rt,int l,int r){ node[rt].l=l;node[rt].r=r; if(l==r){ node[rt].v=a[l]; return; } int mid=l+r>>1; build(lson); build(rson); node[rt].v=node[rt<<1].v+node[rt<<1|1].v; } inline void pushup(int rt){ int t=rt<<1; mrk[t]+=mrk[rt]; mrk[t|1]+=mrk[rt]; node[t].v+=mrk[rt]*(node[t].r-node[t].l+1); node[t|1].v+=mrk[rt]*(node[t|1].r-node[t|1].l+1); mrk[rt]=0; } void add(int rt,int l,int r){ if(L<=l&&r<=R){ node[rt].v+=v*(r-l+1); mrk[rt]+=v; return; } if(mrk[rt])pushup(rt); int mid=l+r>>1; if(R<=mid)add(lson); else if(L>mid)add(rson); else add(lson),add(rson); node[rt].v=node[rt<<1].v+node[rt<<1|1].v; } LL get(int rt,int l,int r){ if(L<=l&&r<=R) return node[rt].v; int mid=l+r>>1; if(mrk[rt])pushup(rt); if(R<=mid)return get(lson); else if(L>mid)return get(rson); else return get(lson)+get(rson); } int main(){ int i,j,x,y; scanf("%d%d",&n,&m); for(i=1;i<=n;++i){ scanf("%lld",&a[i]); a[i]+=a[i-1]; } build(1,1,n); while(m--){ scanf("%d%d%lld",&y,&x,&v); if(y==1){ L=x;R=n; add(1,1,n); } else{ L=x;R=(int)v; LL ans=get(1,1,n); if(x>1){ L=x-1;R=x-1; ans-=get(1,1,n)*(v-x+1); } printf("%lld ",ans); } } return 0; }
再附上树状数组代码
#include <cstdio> #include <iostream> #include <cstdlib> #include <cstring> #include <algorithm> #include <cmath> #include <queue> using namespace std; const int N=100010; typedef long long ll; ll c[2][N]; int n; void add(int p,int x,ll y){while(x<=n){c[p][x]+=y;x+=x&-x;}} ll query(int p,int x){ll r=0;while(x){r+=c[p][x];x-=x&-x;}return r;} int main(){ int q,i,ty; ll x,y,ans; scanf("%d %d",&n,&q); for(i=1;i<=n;i++){ scanf("%lld",&x); add(0,i,x); add(1,i,i*x); } for(i=1;i<=q;i++){ scanf("%d %lld %lld",&ty,&x,&y); if(ty==1){ add(0,x,y); add(1,x,x*y); } else{ ans=(y+1)*(query(0,y)-query(0,x-1))-(query(1,y)-query(1,x-1)); printf("%lld ",ans); } } return 0; }