线段树(模板)
题目: P3372 【模板】线段树 1
线段树:存线段 除建树外,其余操作的复杂度大部分都为O(lgn) 建一个叶子,首先要访问这个叶子,访问一个叶子的复杂度为O(lgn) 所以建n个叶子的复杂度为O(nlgn) 所以建树的复杂度为O(nlgn) 相对于差分,线段树可以边修改边查询 二叉树的性质可以简单推导,不用记
#include<bits/stdc++.h> using namespace std; #define ll long long int const N=1e5+7; int n,m; int a[N]; int lazy[N<<2]; //懒标记 ll tree[N<<2]; void bulid(int p,int l,int r){ if(l==r){ tree[p]=a[l];return ; } int mid=(l+r) >> 1; //l加上r,再除以2 bulid(p*2,l,mid); bulid(p*2+1,mid+1,r); tree[p]=tree[p*2]+tree[p*2+1]; } void pushdown(int p,int len){ lazy[p*2]+=lazy[p]; lazy[p*2+1]+=lazy[p]; tree[p*2]+=(len-len/2)*lazy[p]; tree[p*2+1]+=(len>>1)*lazy[p]; lazy[p]=0; } void add(int p,int l,int r,int x,int y,int z){ if(x<=l&&r<=y){ //(x,y)包含(l,r),即(x,y)更大 像这样:(x (l,r) y) lazy[p]+=z; tree[p]+=( (long long) (r-l+1) )*z; return ; } if(lazy[p]!=0) pushdown(p,r-l+1); int mid=(l+r) >> 1; if(x<=mid) add(p*2,l,mid,x,y,z) ; // x<=mid 代表有左边(左子树),就进左边 if(y>=mid+1) add(p*2+1,mid+1,r,x,y,z); // y>mid 代表有右边(右子树),就进右边 tree[p]=tree[p*2]+tree[p*2+1]; } ll ask(int p,int l,int r,int x,int y){ if(x<=l&&r<=y) return tree[p]; if(lazy[p]!=0) 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(y>=mid+1) res+=ask(p*2+1,mid+1,r,x,y); return res; /*以下是第二种搜索方法,为了方便和统一,以后线段树区间访问都用第一种 if(y<=mid) return find(p*2,l,mid,x,y); if(x>=mid+1) return find(p*2+1,mid+1,r,x,y); return find(p*2,l,mid,x,mid)+find(p*2+1,mid+1,r,mid+1,y); */ } int main(){ cin >> n >> m; for(int i=1;i<=n;++i) cin >> a[i]; bulid(1,1,n); while(m--){ int a; cin >> a; if(a==1){ int b,c,d;cin >> b >> c >> d; add(1,1,n,b,c,d); //第一个1表示从根(第一个点)开始搜索目标区间,然后修改,tree的一号位置表示(1,n)的状态,所以区间是1到n } else{ int b,c;cin >> b >> c; cout << ask(1,1,n,b,c) << endl; } } return 0; }