显然是不能直接开两个树状数组维护 前缀和，前缀和的前缀和。因为一旦对a[i]进行修改，将会影响许多位前缀和的前缀和
我们考虑对式子变一下形
Qi =S1+S2+S3+...+Si
=a1+a1+a2+a1+a2+a3+...+ai =a1*i+a2*(i-1)+a3*(i-2)+...+ai* =(a1+a2+a3+...+ai)*i - (a2+a3^2+a4^3+...+ai^(i-1))因此还是开两个树状数组 一个维护前半部分 一个维护后半部分
#include<bits/stdc++.h> #define N 100005 using namespace std; typedef long long ll; struct BIT { ll tree[N]; int n; inline int lowbit(int x) { return x&(-x); } inline void update(int x,ll del) { for(int i=x;i<=n;i+=lowbit(i)) tree[i]+=del; } inline ll query(int x) { ll ans=0; for(int i=x;i;i-=lowbit(i)) ans+=tree[i]; return ans; } }tree1,tree2; template<class T> inline void read(T &x) { x=0; static char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } int n,m; ll a[N]; int main() { read(n); read(m); tree1.n=n; tree2.n=n; for(int i=1;i<=n;i++) { read(a[i]); tree1.update(i,a[i]); tree2.update(i,a[i]*(i-1)); } char s[10]; for(int i=1;i<=m;i++) { scanf("%s",&s); ll x,y; if(s[0]=='Q') { read(x); cout<<ll(tree1.query(x)*x)-tree2.query(x)<<'\n'; } else { read(x); read(y); tree1.update(x,y-a[x]); tree2.update(x,(y-a[x])*(x-1)); a[x]=y; } } return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9850403.html
