Day52树状数组 线段树（lazy标记）

动态求连续区间和 树状数组是利用lowbit的性质求前缀和

lowbit(x)=$2^k$,k的意思是x的二进制表达最后面有几位0 然后c[x]是对$[x-2^k,x]$范围内的q求和 然后修改，询问区间和都用到这个性质

#include<vector> #include<cstring> #include<cstdio> #include<iostream> #include<string> #include<map> #include<queue> #include<algorithm> #include<ctime> #include<cmath> #include<cstdlib> #define lson (o<<1) #define rson (o<<1|1) #define fi first #define sc second #define dbg(x) cout<<#x<<" = "<<(x)<<endl; #define rg register typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; using namespace std; const double pi=acos(-1); const double eps=1e-6; inline int lowbit(int x){return x&(-x);} template<typename A,typename B,typename C> inline A fpow(A x,B p,C yql){ A ans=1; for(;p;p>>=1,x=1LL*x*x%yql)if(p&1)ans=1LL*x*ans%yql; return ans; } inline int read() { int X=0,w=1; char c=getchar(); while(c<'0'||c>'9') { if (c=='-') { w=-1; } c=getchar(); } while(c>='0'&&c<='9') { X=(X<<3)+(X<<1)+(c^48); c=getchar(); } return X*w; } //inline void w(int x) { if(x>9) w(x/10); putchar(x%10+'0'); } const int N=1e5+10; ll T; int q[N],c[N],n,m; #define lowbit(x) (x&-x) void add(int a,int b){ for(int i=a;i<=n;i+=lowbit(i)){ c[i]+=b; } } int getsum(int a){ int res=0; for(int i=a;i;i-=lowbit(i)){ res+=c[i]; } return res; } void solve(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>q[i]; add(i,q[i]); } int op,a,b; for(int i=0;i<m;i++){ cin>>op>>a>>b; if(op==0){ cout<<getsum(b)-getsum(a-1)<<endl; }else { add(a,b); } } } int main(){ std::ios::sync_with_stdio(0); std::cin.tie(0); T=1; //cin>>T; while(T--){ solve(); } return 0; }

数星星 注意增加星星的时候是增加在32000范围内的星星 所以add的范围扩大到32000

然后要注意y是递增输入的 所以可以直接一行一行的增加我们的树状数组

#include<vector> #include<cstring> #include<cstdio> #include<iostream> #include<string> #include<map> #include<queue> #include<algorithm> #include<ctime> #include<cmath> #include<cstdlib> #define lson (o<<1) #define rson (o<<1|1) #define fi first #define sc second #define dbg(x) cout<<#x<<" = "<<(x)<<endl; #define rg register typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; using namespace std; const double pi=acos(-1); const double eps=1e-6; inline int lowbit(int x){return x&(-x);} template<typename A,typename B,typename C> inline A fpow(A x,B p,C yql){ A ans=1; for(;p;p>>=1,x=1LL*x*x%yql)if(p&1)ans=1LL*x*ans%yql; return ans; } inline int read() { int X=0,w=1; char c=getchar(); while(c<'0'||c>'9') { if (c=='-') { w=-1; } c=getchar(); } while(c>='0'&&c<='9') { X=(X<<3)+(X<<1)+(c^48); c=getchar(); } return X*w; } //inline void w(int x) { if(x>9) w(x/10); putchar(x%10+'0'); } const int N=32010; ll T; int q[N],level[N],n,ans[N]; void add(int a){ for(int i=a;i<=N;i+=lowbit(i)){ level[i]++; } } int getsum(int a){ int res=0; for(int i=a;i;i-=lowbit(i)){ res+=level[i]; } return res; } void solve(){ cin>>n; int x,y; for(int i=0;i<n;i++){ cin>>x>>y; x++; ans[getsum(x)]++; add(x); } for(int i=0;i<n;i++)cout<<ans[i]<<endl; } //01122 int main(){ std::ios::sync_with_stdio(0); std::cin.tie(0); T=1; //cin>>T; while(T--){ solve(); } return 0; }

---

线段树 下面是query中l和r不修改的原因 因为tr[u].l+tr[u].r>>1和区间毫无关系 甚至可能扩大查询区间 比如下面查询[1，3] 就会把3扩大成5 从而查询到45的结果 线段树

#include<vector> #include<cstring> #include<cstdio> #include<iostream> #include<string> #include<map> #include<queue> #include<algorithm> #include<ctime> #include<cmath> #include<cstdlib> #define lson (o<<1) #define rson (o<<1|1) #define fi first #define sc second #define dbg(x) cout<<#x<<" = "<<(x)<<endl; #define rg register typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; using namespace std; const double pi=acos(-1); const double eps=1e-6; inline int lowbit(int x){return x&(-x);} template<typename A,typename B,typename C> inline A fpow(A x,B p,C yql){ A ans=1; for(;p;p>>=1,x=1LL*x*x%yql)if(p&1)ans=1LL*x*ans%yql; return ans; } inline int read() { int X=0,w=1; char c=getchar(); while(c<'0'||c>'9') { if (c=='-') { w=-1; } c=getchar(); } while(c>='0'&&c<='9') { X=(X<<3)+(X<<1)+(c^48); c=getchar(); } return X*w; } //inline void w(int x) { if(x>9) w(x/10); putchar(x%10+'0'); } const int N=1e5+10; ll T; struct node{ int l,r,sum; }tr[N*4]; int q[N]; void pushup(int u){ tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum; } void build(int u,int l,int r){ if(l==r){ tr[u]={l,r,q[l]}; return; } tr[u]={l,r}; int mid=l+r>>1; build(u<<1,l,mid); build(u<<1|1,mid+1,r); pushup(u); } int query(int u,int l,int r){ if(tr[u].l>=l&&tr[u].r<=r){ return tr[u].sum; } int mid=tr[u].l+tr[u].r>>1; int sum=0; if(l<=mid)sum=query(u<<1,l,r); if(r>mid)sum+=query(u<<1|1,l,r); return sum; } void add(int u,int x,int v){ if(tr[u].l==tr[u].r){ tr[u].sum+=v; return; } int mid=tr[u].l+tr[u].r>>1; if(x<=mid)add(u<<1,x,v); else add(u<<1|1,x,v); pushup(u); } void solve(){ int n,m; cin>>n>>m; for(int i=1;i<=n;i++){ cin>>q[i]; } build(1,1,n); int op,a,b; for(int i=0;i<m;i++){ cin>>op>>a>>b; if(op){ add(1,a,b); }else{ cout<<query(1,a,b)<<endl; } } } int main(){ std::ios::sync_with_stdio(0); std::cin.tie(0); T=1; //cin>>T; while(T--){ solve(); } return 0; }

lazy标记的线段树

#include<vector> #include<cstring> #include<cstdio> #include<iostream> #include<string> #include<map> #include<queue> #include<algorithm> #include<ctime> #include<cmath> #include<cstdlib> #define lson (o<<1) #define rson (o<<1|1) #define fi first #define sc second #define dbg(x) cout<<#x<<" = "<<(x)<<endl; #define rg register typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; using namespace std; const double pi=acos(-1); const double eps=1e-6; inline int lowbit(int x){return x&(-x);} template<typename A,typename B,typename C> inline A fpow(A x,B p,C yql){ A ans=1; for(;p;p>>=1,x=1LL*x*x%yql)if(p&1)ans=1LL*x*ans%yql; return ans; } inline int read() { int X=0,w=1; char c=getchar(); while(c<'0'||c>'9') { if (c=='-') { w=-1; } c=getchar(); } while(c>='0'&&c<='9') { X=(X<<3)+(X<<1)+(c^48); c=getchar(); } return X*w; } //inline void w(int x) { if(x>9) w(x/10); putchar(x%10+'0'); } const int N=1e5+10; ll T; struct node{ int l,r; ll sum,add; #define l(x) tree[x].l #define r(x) tree[x].r #define sum(x) tree[x].sum #define add(x) tree[x].add }tree[4*N]; ll q[N]; void build(int u,int l,int r){ l(u)=l,r(u)=r; if(l==r){ sum(u)=q[l]; return; } int mid=l+r>>1; build(u<<1,l,mid); build(u<<1|1,mid+1,r); sum(u)=sum(u<<1)+sum(u<<1|1); } void spread(int u){ if(add(u)){ sum(u<<1)+=add(u)*(r(u<<1)-l(u<<1)+1); sum(u<<1|1)+=add(u)*(r(u<<1|1)-l(u<<1|1)+1); add(u<<1)+=add(u); add(u<<1|1)+=add(u); add(u)=0; } } void change(int u,int l,int r,int v){ if(l(u)>=l&&r(u)<=r){ sum(u)+=(ll)v*(r(u)-l(u)+1); add(u)+=v; return; } spread(u); int mid=l(u)+r(u)>>1; if(l<=mid)change(u<<1,l,r,v); if(r>mid)change(u<<1|1,l,r,v); sum(u)=sum(u<<1)+sum(u<<1|1); } ll query(int u,int l,int r){ if(l(u)>=l&&r(u)<=r){ return sum(u); } spread(u); int mid=l(u)+r(u)>>1; ll sum=0; if(l<=mid)sum+=query(u<<1,l,r); if(r>mid) sum+=query(u<<1|1,l,r); return sum; } void solve(){ int n,m; cin>>n>>m; for(int i=1;i<=n;i++)cin>>q[i]; build(1,1,n); int op,x,y; while(m--){ cin>>op; if(op==1){ cin>>x>>y; change(1,x,x,y); }else { cin>>x>>y; cout<<query(1,x,y)<<endl; // query(1,x,y); } } } int main(){ std::ios::sync_with_stdio(0); std::cin.tie(0); T=1; //cin>>T; while(T--){ solve(); } return 0; }

最好把lson和rson封装

真的会写错。。。。

然后注意mid缩小范围只在build中出现 spread要在判断完边界后立刻执行