P3368的题解

letianJOE · 2023-12-21 19:20:27 · 题解

题目大意

用树状数组实现区间修改和单点查询。

思路

模板题

思考点

区间修改，单点查询的线段树需要维护差分数组而不是前缀和数组。

证明两个点就懂了。

假设 a 为原数组，b 为差分数组。

和

• 如果 a 数组 [l,r] 内所有数都加上 k 的，那么 b 数的变化 b_l \gets (b_l+k) , b_{r+1} \gets (b_{r+1}-k)

上面性质的证明

这样就可以实现单点查询和区间修改的操作了。

单点查询输出 ask(i)。

区间修改进行 add(x,k),add(y+1,-k) 的操作。

CODE

//模板
/*
树状数组 
区间修改+单点查询。
*/ 
#include<bits/stdc++.h>
using namespace std;
const int N=5*1e5; 
int n,m;
int a[N+5];
int bin[N+5];
int lowbit(int x)
{
    return x&(-x);
}
void add(int x,int k)
{
    for(int i=x;i<=n;i+=lowbit(i))
        bin[i]+=k;
    return ;
}
int ask(int x)
{
    int cnt=0;
    for(int i=x;i>=1;i-=lowbit(i))
        cnt+=bin[i];
    return cnt;
}
main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
        add(i,a[i]-a[i-1]);
    while(m--)
    {
        int op;
        cin>>op;
        if(op==1)
        {
            int l,r,k;
            cin>>l>>r>>k;
            add(l,k),add(r+1,-k); 
        }
        else
        {
            int x;
            cin>>x; 
            cout<<ask(x)<<"\n";
        }
    }
    return 0;
}
/*
5 5
1 5 4 2 3
1 2 4 2
2 3
1 1 5 -1
1 3 5 7
2 4
*/
/*
6
10
*/