线段树
线段树
线段树是树状数组的强化版，它每次对区间进行二分，每一个深度都维护了整个区间，在同一深度里面，每个节点维护的区间长度大致相同，而每深入一层又大致比上一层多一倍的节点，故空间复杂度为Onlgn节点信息
每个非叶子节点维护一个区间[l,r]，令mid=(l+r)>>1,则该节点的左儿子维护[l,mid]，右儿子维护[mid+1,r]；每个叶子节点维护一个点；
线段树的平衡性
线段树是一颗几乎完全平衡的树。线段树的区间操作
因此当我们对于一个长度为n区间[l,r]进行操作的时候，我们就要操作所有与这些区间相关节点，这些节点数目接近2*N。要操作2*N个节点，，，，复杂度过高，，，问题无法解决。我们的操作相当于对树进行函数递归。
对节点分类
这里我们把这个问题简化一下，对于那些节点对应区间属于[l,r]的我们分为一类，对于那些节点对应区间与[l,r]有交集，但不是[l,r]的子区间的节点我们分为第二类，第二类节点一定是某个第一类节点的父亲节点，借此我们可以在函数回溯时候利用区间加法处理，容易解决。继续分析复杂度
我们容易发现第一类节点数目接近ON而第二类节点数目接近OlgN，第二类节点一个一个处理可以接受，第一类节点必须安排一下。可以证明第一类节点恰好可以用OlgN颗子树的所有节点唯一表达。在这里我们简化问题为对于OlgN个节点以及OlgN颗子树的操作，
子树的操作
现在我们只需要考虑对某颗子树进行操作懒惰标记（懒修改）
当我们进行修改的时候，我们试着只对该子树的根进行修改，并为其加入一个懒惰标记，表示他的所有子孙都有一个与懒惰标记有关的操作还未进行，(例如整段区间加上d，我们就设懒惰标记为d) ，如此区间修改就不用跑到叶子节点，就成了OlgN当我们进行查询时，每当我们查询一个节点，我们要查询的恰好为该节点所对应的区间，直接就处理了；如果不是该区间，而是该区间的某个子区间，那么我们考虑把该区间的懒惰标记下放到左右儿子，然后递归左右儿子，回溯答案。over
为什么线段树快，因为它把区间分成OlgN个处理，并且每次在树上只跑了OlgN个节点，依据区间加法处理询问，依据区间加法回溯处理修改，依据懒惰标记不实时更新叶子节点。所以线段树快。
线段树和树状数组
为什么我在开头说线段树是树状数组的强化版，因为树状数组虽然能依据区间加法处理询问，也可以依靠区间加法处理更新，但是它的非叶子节点过少，导致复杂的数据维护时程序较为复杂，不太好处理。#define ls (u<<1) #define rs (u<<1|1) #define ml ((l+r)>>1) #define mr (ml+1) struct segment_tree{ static const ll maxn=2.1e5; ll n; ll a[maxn],tree[maxn<<2],lazy[maxn<<2]; ////////////// //树链剖分接口 ll rnk[maxn]; ////////////// void pushdown(ll u,ll l,ll r){ //lazy[ls]+=lazy[u]; //lazy[rs]+=lazy[u]; //tree[ls]+=lazy[u]*(ml-l+1); //tree[rs]+=lazy[u]*(r-mr+1); lazy[u]=0; } void pushup(ll u){ //tree[u]=tree[ls]+tree[rs]; } void build(ll nn){ n=nn; build(1,n,1); } void build(ll l,ll r,ll u){ lazy[u]=0; if(l==r){ //tree[u]=a[rnk[l]]; return ; } build(l,ml,ls); build(mr,r,rs); pushup(u); } void update(ll ql,ll qr,ll d){ update(ql,qr,d,1,1,n); } void update(ll ql,ll qr,ll d,ll u,ll l,ll r){ if(ql<=l&&r<=qr){ //tree[u]+=(r-l+1)*d; //lazy[u]+=d; return ; } if(lazy[u])pushdown(u,l,r); if(ql<=ml)update(ql,qr,d,ls,l,ml); if(qr>=mr)update(ql,qr,d,rs,mr,r); pushup(u); } ll query(ll ql,ll qr){ return query(ql,qr,1,1,n); } ll query(ll ql,ll qr,ll u,ll l,ll r){ if(ql<=l&&r<=qr)return tree[u]; ll ret=0; if(lazy[u])pushdown(u,l,r); if(ql<=ml)ret+=query(ql,qr,ls,l,ml); if(qr>=mr)ret+=query(ql,qr,rs,mr,r); return ret; } };
#define ml ((l+r)>>1) #define mr (ml+1) const int maxn=5e4+5; int rev[maxn*2*35],cov[maxn*2*35],sum[maxn*2*35],ls[maxn*2*35],rs[maxn*2*35],a[maxn],tot; void push_son(int&son,int l,int r,int covrt,int revrt){// 这个函数要注意重写 if(son==0) { son=++tot; cov[son]=-1; rev[son]=0; sum[son]=0; ls[son]=0; rs[son]=0; } if(covrt!=-1){ sum[son]=(r-l+1)*covrt; cov[son]=covrt; rev[son]=0; } if(revrt!=0){ sum[son]=(r-l+1)-sum[son]; rev[son]^=1; } } void push_down(int rt,int l,int r){ push_son(ls[rt],l,ml,cov[rt],rev[rt]);// 这行要注意重写 push_son(rs[rt],mr,r,cov[rt],rev[rt]);// 这行要注意重写 cov[rt]=-1; rev[rt]=0;// 这行要注意重写 } void push_up(int rt,int l,int r){ sum[rt]=sum[ls[rt]]+sum[rs[rt]];// 这行要注意重写 } void build(int&rt,int l,int r){ rt=tot=0; push_son(rt,l,r,-1,0);// 这行要注意重写 } void update(int rt,int l,int r,int ql,int qr,int d,int type){// if(ql<=l&&r<=qr){// 这行要注意重写 if(type==1) push_son(rt,l,r,-1,1);//rev if(type==2) push_son(rt,l,r, d,0);//cover return; } push_down(rt,l,r); if(ml>=ql) update(ls[rt],l,ml,ql,qr,d,type); if(mr<=qr) update(rs[rt],mr,r,ql,qr,d,type); push_up(rt,l,r); } int query(int rt,int l,int r,int ql,int qr){ if(ql<=l&&r<=qr) return sum[rt];// 这行要注意重写 push_down(rt,l,r); int ret=0;// 这行要注意重写 if(ml>=ql) ret+=query(ls[rt],l,ml,ql,qr);// 这行要注意重写 if(mr<=qr) ret+=query(rs[rt],mr,r,ql,qr);// 这行要注意重写 return ret; }
