树状数组（2019.7.22训练）

洛谷 P3374 【模板】树状数组 1

单点修改，区间查询和。

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,m,x,y,opt,a[N];
void update(int i,int v)
{
    while(i<=n)
    {
        a[i]=a[i]+v;
        i=i+(i&-i);
    }
}
int sum(int i)
{
    int s=0;
    while(i)
    {
        s=s+a[i];
        i=i-(i&-i);
    }
    return s;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        update(i,x);
    }
    while(m--)
    {
        cin>>opt>>x>>y;
        if(opt==1)update(x,y);
        else printf("%d\n",sum(y)-sum(x-1));
    }
    return 0;
}

洛谷 P3368 【模板】树状数组 2

区间修改，单点查询。维护差分数组即可。

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,m,x,y,k,opt,a[N],ans[N];//原数组为a[i]，其差分数组保存在树状数组ans[i]中
void update(int i,int v)
{
    while(i<=n)
    {
        ans[i]=ans[i]+v;
        i=i+(i&-i);
    }
}
int sum(int i)
{
    int s=0;
    while(i)
    {
        s=s+ans[i];
        i=i-(i&-i);
    }
    return s;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        x=a[i]-a[i-1];//求差分
        update(i,x);
    }
    while(m--)
    {
        cin>>opt;
        if(opt==1)
        {
            cin>>x>>y>>k;
            update(x,k);
            update(y+1,-k);
        }
        else
        {
            cin>>x;
            printf("%d\n",sum(x));
        }
    }
    return 0;
}