XOR的艺术
tr[p]除了表示区间p中1的和,也表示区间p中1的个数
懒标记ly[p]表示其左右儿子区间(tr[p* 2] 和 tr[p*2+1] )的待操作次数
tr[p]的待操作次数是ly[p/2]
当add到p时,tr[p]一定要更新(记住)
懒标记是线段树的灵魂,没有懒标记,线段树比朴素修改还要慢
#include<bits/stdc++.h> using namespace std; #define ll long long int const N=2e5+7; ll tr[N<<2],ly[N<<2],a[N]; void bulid(int p,int l,int r){ if(l==r){ tr[p]=a[l];return ; } int mid=(l+r) >> 1; bulid(p*2,l,mid); bulid(p*2+1,mid+1,r); tr[p]=tr[p*2]+tr[p*2+1]; } void pushdown(int p,int len){ if(ly[p]%2){ ly[p*2]++;ly[p*2]%=2; tr[p*2]=len-len/2-tr[p*2]; ly[p*2+1]++;ly[p*2+1]%=2; tr[p*2+1]=len/2-tr[p*2+1]; } ly[p]=0; } void add(int p,int l,int r,int x,int y){ if(x<=l&&r<=y){ ly[p]++;ly[p]%=2; tr[p]=r-l+1-tr[p]; return ; } pushdown(p,r-l+1); int mid=(l+r)>>1; if(x<=mid) add(p*2,l,mid,x,y); if(mid+1<=y) add(p*2+1,mid+1,r,x,y); tr[p]=tr[p*2]+tr[p*2+1]; } ll ask(int p,int l,int r,int x,int y){ if(x<=l&&r<=y){ return tr[p]; } pushdown(p,r-l+1); int mid=(l+r)>>1; ll res=0; if(x<=mid) res+=ask(p*2,l,mid,x,y); if(mid+1<=y) res+=ask(p*2+1,mid+1,r,x,y); return res; } int n,m; int main(){ cin >> n >> m; string str; cin >> str; for(int i=0;i<str.size();++i){ a[i+1]=str[i]-'0'; } bulid(1,1,n); int op,x,y; while(m--){ cin >> op >> x >> y; if(op==0) add(1,1,n,x,y); else cout << ask(1,1,n,x,y) << "\n"; } return 0; }
线段树和数状数组经典例题 文章被收录于专栏
线段树和数状数组经典例题