每日速讯：F - 树状数组 2【GDUT_22级寒假训练专题五】

2023-02-19 12:08:32 来源：博客园

(资料图片)

F - 树状数组 2

原题链接

思路

在树状数组1中我们可以得知

单点修改，区间查询（区间和）对原数组进行单点修改，对区间和进行树状数组维护

利用差分和前缀和我们可以推导出

区间修改（差分），单点查询原数组 = 差分的前缀和数组对差分数组进行单点修改实现区间修改，对差分的前缀和数组（即原数组）进行树状数组维护实现单点查询

代码

点击查看代码

#include#include#include#include#include#include#includeusing namespace std;#define X first#define Y secondtypedef pair pii;typedef long long LL;const char nl = "\n";const int N = 5e5+10;const int M = 2e5+10;int n,m;LL a[N],d,b[N];int lowbit(int x){return x & -x;}void add(int k,int x){while(k <= n){b[k] += x;k += lowbit(k);}}LL getsum(int l,int r){l --;LL s1 = 0;while(l){s1 += b[l];l -= lowbit(l);}LL s2 = 0;while(r){s2 += b[r];r -= lowbit(r);}return s2 -s1;}void solve(){cin >> n >> m;for(int i = 1; i <= n; i ++ ){cin >> a[i];//原数组d = a[i] - a[i-1];//差分数组add(i,d);//对差分数组的前缀和进行树状数组维护}while(m --){int op;cin >> op;if(op == 1){int l,r,x;cin >> l >> r >> x;add(l,x);//差分add(r+1,-x);//差分}else{//输出s[k]差分数组(1,k)的和int k;cin >> k;cout << getsum(1,k) << nl;}}}int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);solve();}

关键词：区间查询点击查看