壹、题目大意
给出长度为 \(n\) 的序列 \(a_1 \sim a_n\)，设 \(S_i = \sum\limits_{j=1}^i a_j\)，有两种操作
可以给定 \(i\) 和 \(x\)，使得 \(a_i = x\)，也可以给定 \(i\)，查询 \(\sum\limits_{j=1}^i S_j\) 的值
\(n \le 100000\)
贰、思路
这道题查询的是 \(S\)，但实际上是 \(a\)，而操作一中修改 \(a_i\) 也会影响到 \(S_i \sim S_n\) 的值，从而影响操作二
因此考虑维护 \(a\)
由上文，修改 \(a_i\) 会影响到 \(S_i \sim S_n\)，所以我们知道操作一实际上就是对 \(S\) 区间加
查询 \(\sum\limits_{j=1}^i S_j\)，实际上就是查询 \(1 \sim i\) 中各个 \(S\) 的和
因此操作二实际上就是对 \(S\) 区间查询（是特殊的，从 \(1\) 开始）
由此，我们可以想到线段树、分块、树状数组等做法
线段树时间复杂度 \(O(n log_2 n)\)，但常数大，代码编写难度大，可以先放弃
分块时间复杂度 \(O(n \sqrt{n})\)，这道题 \(n\) 取 \(100000\) 时接近 \(10^7\) 级别，容易被卡，可以暂时搁置
树状数组的话时间复杂度 \(O(n log_2 n)\)，但常数小，代码编写难度小，对于区间查询手到擒来；
因此优先考虑树状数组
对于区间修改我们看到修改的是 \(i \sim n\)中的 \(S\) 的，可以用差分；但差分有些繁琐，而且差分是对于单点查询的，那如何不差分呢？
因此考虑好数据结构，还要再思考一个问题：如何把题目中问的与 \(a\) 无关的式子推成与 \(a\) 有关的式子
OI中，推导式子是一个常态
遇到这种有累加值的题目，我们可以首先把题目中的原式转化成与输入的 \(a\) 有关联的内容：
\[\sum\limits_{j=1}^i S_j = \sum\limits_{j=1}^i \{ \sum\limits_{k=1}^j a_k \} \]然后我们举一些特殊例子来判断：
\(a_1\) 被 \(1 \sim i\) 的每一个 \(S\) 都计算了一遍，一共计算了 \(i-1+1=i\) 次
\(a_2\) 被 \(2 \sim i\) 的每一个 \(S\) 都计算了一遍，一共计算了 \(i-2+1=i-1\) 次
…………
\(a_i\) 被 \(i \sim i\) 的每一个 \(S\) 都计算了一边，一共计算了 \(i-i+1=1\) 次
然后我们可以发现，对于一个 \(a_k\)，它对 \(1 \sim i\) 的这么一个查询，如果设它的 贡献 为它为答案贡献的数值，
那它的 贡献 便是它本身的数值乘上它在前缀和里面出现的次数，即 \(Contribute(k)=a_k \cdot cnt_k=a_k \cdot (i-k+1)\)
每个 \(a_k\) 的贡献之和便是要查询的答案
所以
\[\sum\limits_{j=1}^i \{ \sum\limits_{k=1}^j a_k \} = \sum\limits_{j=1}^i Contribute(j) = \sum\limits_{j=1}^i \{ a_j \cdot (i-j+1) \} \]拆开，得到
\[(i+1) \cdot \sum\limits_{j=1}^i a_j - \sum\limits_{j=1}^i \{a_j \cdot j\} \]拆到这里，想必大家都明白了，这里有两个前缀和：\(a_j\) 和 \(a_j \cdot j\)
所以我们需要维护两个树状数组，一个里面是 \(a_j\) ，另一个里面是 \(a_j \cdot j\)
然后按照这个式子写出来即可
（注意树状数组大小范围）
叄、代码
#include<bits/stdc++.h>
#define endl "\n"
#define int long long//要开 long long
using namespace std;
const int N=100009;
int n,m;
int a[N];
class tree_array
{
private:
int s[N<<1];
inline int lowbit(int x){return x&(-x);}
public://模板操作
inline void add(int point,int val)
{
for(int i=point;i<=(n<<1);i+=lowbit(i)) s[i]+=val;
return;
}
inline int query(int point)
{
int res=0;
for(int i=point;i>=1;i-=lowbit(i)) res+=s[i];
return res;
}
}bit1,bit2;
//bit1 维护 aj，bit2 维护 aj*j
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
//freopen("sum.in","r",stdin);
//freopen("sum.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];//输入
for(int i=1;i<=n;i++)
{
bit1.add(i,a[i]);
bit2.add(i,a[i]*i);//建立树状数组
}
while(m--)
{
string str;
int u,x;
cin>>str>>u;
if(str=="Modify")
{
cin>>x;
bit1.add(u,x-a[u]);
bit2.add(u,(x-a[u])*u);//修改一下
a[u]=x;
}
else
{
int res=(u+1)*bit1.query(u)-bit2.query(u);//按照推的式子输出即可
cout<<res<<endl;
}
}
return 0;
}