壹、题目大意

给出长度为 \(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;
}