树状数组板子(维护前缀和)

#include<iostream>
 #include<cmath>
 #include<algorithm>
 #include<cstring>
 #include<queue>
using namespace std;
typedef long long ll;
const int NS=5e5+5;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int tree[NS];
int sum[NS];
int lowbit(int t)
{
    return t&(-t);
}
void update(int x,int y,int n)
{
    for(int i=x;i<=n;i+=lowbit(i))
        tree[i]+=y;
}
int query (int z)
{
    long long sum=0;
    for(int i=z;i>=1;i-=lowbit(i))
        sum+=tree[i];
    return sum;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {cin>>sum[i];}
    while(m--)
    {
        int a,x,y,z;
        cin>>a;
        if(a==1)
        {
            cin>>x>>y>>z;
            update(x,z,n);
            update(y+1,-z,n);
        }
        else
        {
            cin>>z;
            cout<<sum[z]+query(z)<<\n;
        }

    }
}

 

树状数组板子(维护前缀和)

上一篇:【算法框架套路】回溯算法(暴力穷举的艺术)


下一篇:川川数模-D4-多元线性回归模型