题目地址:https://www.luogu.org/problemnew/show/P3368

题目:


 

《算法笔记》那本书最后几页有介绍这种问题,但是我按照那种思路写不出来。。太弱了。。不懂

网上都是下面这种代码,目前树状数组一知半解吧,先暂时记住。

ac代码:


#include <iostream>
#include <algorithm>
#include <string.h>
#include <ctype.h>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <fstream>
#define  maxn 500005
#define lowbit(x) ((x)&(-x))
typedef long long ll;
using namespace std;
ll n,m,op,l,r,v,now,last=0,pos,c[maxn]={0};
void update(ll x,ll v)
{
    for(ll i=x;i<=n;i+=lowbit(i))
        c[i]+=v;
}
ll getvalue(ll x)
{
    ll sum=0;
    for(ll i=x;i>0;i-=lowbit(i))
        sum+=c[i];
    return sum;
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%lld %lld",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&now);
        update(i,now-last);
        last=now;
    }
    for(int i=0;i<m;i++)
    {
        scanf("%lld",&op);
        if(op==1)
        {
            scanf("%lld %lld %lld",&l,&r,&v);
            update(l,v);
            update(r+1,-v);
        }
        else
        {
            scanf("%lld",&pos);
            printf("%lld\n",getvalue(pos));
        }
    }
    return 0;
}