【BZOJ 3155】Preprefix sum(树状数组)
显然是不能直接开两个树状数组维护 前缀和,前缀和的前缀和。因为一旦对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