题解 P2068 【统计和】

yyk504 · 2019-04-13 20:20:15 · 题解

这题楼下各位dalao们线段树、树状数组666

其实这题是一个弱化的树状数组/线段树

但其实这题可以用前缀和来做我才不告诉你我不会线段树

不懂前缀和的点这里

具体操作看代码

代码

#include<bits/stdc++.h>
using namespace std;
long long p[100010];//这里最好开long long（NOIP2018T2惨痛经历）
int main()
{
    int x,y,i,n,w;
    cin>>n>>w;
    char c;
    for (i=1;i<=w;i++)
    {
        cin>>c>>x>>y;
        if (c=='x') 
        {
            int j;
            for (j=x;j<=n;j++)
            p[j]+=y;//维护数组，自己再理解一下
        }
        else cout<<p[y]-p[x-1]<<endl;//前缀和经典操作
    }
    return 0;
}