树状数组学习笔记

mac2025-02-17  7

树状数组

在学习完了线段树后,听说树状数组能写的题,线段树都能做,所以一直没有详细的学习树状数组;直到碰到了一道卡线段树的题目,因为线段树运用了很多递归,所以常数比较大,容易被卡;现在总结一下树状数组;

学习树状数组前一定要把lowbit这个东西弄懂,建议百度;

1、树状数组个人认为就是前缀和演变而来的; 2、 单点更新:当你要更新某个点的值时,你要从下面到上面依次更新过去; 区间查询和单点查询:树状数组没有区间查询这个东西,都可以说是单点查询,就跟差不多前缀和,当你求区间[l.r]的和时,只要sum( r)-sum(l-1)就行;并且要从上到下依次相加,跟前缀和差不多; 3、 区间更新:这里的区间更新,就跟差分数组非常相似了,当你要求区间[l,r]都加上a时,差分数组是l点加上a,r+1这个点减去a;树状数组跟这一样;也可以说是单点更新;

模板: 1.单点更新+区间查询;求和操作;

#include<bits/stdc++.h> #define LL long long #define pa pair<int,int> #define lson k<<1 #define rson k<<1|1 //ios::sync_with_stdio(false); using namespace std; const int N=500100; const int M=200100; const LL mod=2e9+7; int n,m,tr[N]; int lowbit(int k){ return k & (-k); } void add(int p,int q){//p点加上q,单点修改 while(p<=n){ tr[p]+=q; p+=lowbit(p); } } int sum(int p){//单点查询,就是求前缀和 int s=0; while(p!=0){ s+=tr[p]; p-=lowbit(p); } return s; } int main(){ ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=n;i++){ int x; cin>>x; add(i,x); } for(int i=1;i<=m;i++){ int a,b,c; cin>>a>>b>>c; if(a==1) add(b,c); else cout<<sum(c)-sum(b-1)<<endl; } return 0; }

2.区间更新+单点查询;求和操作

#include<bits/stdc++.h> #define LL long long #define pa pair<int,int> #define lson k<<1 #define rson k<<1|1 //ios::sync_with_stdio(false); using namespace std; const int N=500100; const int M=200100; const LL mod=2e9+7; int n,m,tr[N]; int lowbit(int k){ return k & (-k); } void add(int p,int q){//p点加上q,单点修改 while(p<=n){ tr[p]+=q; p+=lowbit(p); } } int sum(int p){//单点查询,就是求前缀和 int s=0; while(p!=0){ s+=tr[p]; p-=lowbit(p); } return s; } int main(){ ios::sync_with_stdio(false); cin>>n>>m; int last=0; for(int i=1;i<=n;i++){ int x; cin>>x; add(i,x-last);//差分 last=x; } for(int i=1;i<=m;i++){ int a,b,c,d; cin>>a; if(a==1){ cin>>b>>c>>d; add(b,d); add(c+1,-d);//差分的体现 } else{ cin>>b; cout<<sum(b)<<endl; } } return 0; }
最新回复(0)