线段树概念：将[1,n]分解成若干特定的子区间(数量不超过4*n，线段树需要的空间为数组大小的四倍)，然后将每个区间[L，R]都分解为少量特定的区间，通过对这些少量子区间进行修改或者统计，来实现快速对[L，R]的修改或统计。
①：线段树是个树
②：线段树是基于一个数组生成
线段树是一种二叉搜索树，每个区间对应线段树的一个叶节点；线段树是一种工具，可以对区间（或者线段）进行修改、维护，优化时间复杂度从O(n)到O(logn)。
长度为10的线段（区间）图解：
线段树特点：最上面的根节点的权值表示是线段（区间）1~10的和，根的两个儿子分别表示这个线段（区间）中1~5的和、6~10的和，依次递推。
通过对这些区间进行修改、查询，来实现对大区间的修改、查询，每次修改、查询时间复杂度都只能为O(logn)
节点i的权值=左儿子权值+右儿子权值
非叶子节点[a，b]：
①：左儿子--[a，(a+b)/2]
②：右儿子--[(a+b)/2+1，b]
注意：
①：线段树多用于解决区间问题，并不限于解决区间问题
②：使用线段树维护的问题必须满足区间加法
区间加法：一个问题满足区间加法，对于区间[L,R]的问题答案可以由[L,M]和[M+1,R]的答案合并得到
定位与区分：前缀和、树状数组、线段树
前缀和：维护从1到n区间的信息
树状数组：维护从第n个开始数，长度为lowbit(n)的区间信息
线段树：维护[L，R]区间的信息
数组表达的线段树基本性质：
①：树根从1开始，即tree[0]不用，这里线段树下标必须从1开始
②：若根下标是i，则左儿子是tree[2*i]，右儿子是tree[2*i+1]
③：tree的区间如果是[L,R]，tree[2*i]的区间是[L,(L+R)/2]，tree[2*i+1]的区间是[(L+R)/2+1,R]
④：如果L==R，表示区间长度为1，是叶节点
⑤：tree的大小可以设为叶子节点数的4倍，二叉树高度是O(logn)
线段树空间复杂度：4*n
①：假设n=2^i，从第0行（i=0）开始，第i行有2^i个节点
②：一共有i行，节点总数为1+2+4+8+...+2^i=2^(i+1)-2^0
=2*2^i-1=2n-1
③：2^(i-1)=n=2^i---2^i=2n---2*2^i-1--4n-1
线段树构建：
线段树将每个长度不为1的区间划分为左右两个区间，并递归处理，通过合并两个区间的信息来求得该区间的信息
举例子：
①：数组arr=[13,99,23,66,7,2,56,45]
②：数组长度为8，以中点为分界点，划分为左右子区间
递归划分过程：
回溯合并信息：
线段树结构：
简单练习：
方法一：结构体构建
#includeiostreamusingnamespacestd;constintN=5e5+5;//线段树元素structNode{intl,r;//当前节点的区间边界intsum;};inta[N];Nodet[4*N];//更新线段树voidupdate(inti){t.sum=t[2*i].sum+t[2*i+1].sum;}//构建线段树voidbuild(inti,intl,intr){t.l=l;t.r=r;if(l==r){t.sum=a[l];return;}intm=(l+r)1;build(2*i,l,m);//左儿子build(2*i+1,m+1,r);//右儿子update(i);}intmain(){for(inti=1;i=5;i++){cina;}build(1,1,5);for(inti=1;i=9;i++){coutt.sum"";}return0;}
方法二：数组构建
#includeiostreamusingnamespacestd;constintM=5e5+5;inta[M];inttree[4*M];inlineintleft_t(inti){//关键子：inline内联函数，防止频繁调用，调用会有额外开销returni1;}inlineintright_t(inti){return(i1)+1;}inlinevoidupdate(inti){tree=tree[left_t(i)]+tree[right_t(i)];}voidbuild(inti,intl,intr){//递归构建线段树if(l==r){//当长度为1时，叶子节点tree=a[l];return;}intm=(l+r)1;build(left_t(i),l,m);build(right_t(i),m+1,r);update(i);}intmain(){for(inti=1;i=5;i++){cina;}build(1,1,5);for(inti=1;i=9;i++){couttree"";}return0;}
线段树应用：
①：单点修改，区间查询
线段数的主要作用是维护一个区间，比如如果想求区间1~中，50~70这些元素的和，暴力做法就是使用for循环:
for(inti=50;i=70;i++){sum+=a;}
单点修改：
把区间的dis位加上k，从根节点开始，看dis是左儿子还是右儿子，返回的时候，按照tree.sum=tree[2*i].sum+tree[2*i+1].sum原则，更新所有路过的点。
inlinevoidupdate(inti,intdis,intk){if(tree.l==tree.r){//如果是叶子节点，找到了，回溯tree.sum+=k;return;}if(dis=tree[2*i].r){update(2*i,dis,k);//向左}else{update(2*i+1,dis,k);//向右}tree.sum=tree[i*2].sum+tree[i*2+1].sum;//回溯更新}
区间查询：
求1~3的和？
第一步：如果目标区间完全包含当前区间，直接返回当前区间的权值
第二步：如果当前区间的左儿子和目标区间有交集，那么搜索当前区间左儿子
第三步：如果当前区间的右儿子和目标区间有交集，那么搜索当前区间右儿子
inlineintquery(inti,intl,intr){if(tree.l=ltree.r=r){//对应上面第一步returntree.sum;}if(tree.lr
tree.rl){//目标区间和当前区间没关系return0;}ints=0;//如果有关系，但是并不是完全包含if(tree[i*2].r=l){//左儿子与目标区间相交s+=query(i*2,l,r);}if(tree[i*2+1].l=r){//右儿子与目标区间相交s+=query(i*2+1,l,r);}return}
程序代码：
#includeiostreamusingnamespacestd;constintN=5e5+5;//线段树元素structNode{intl,r;//当前节点的区间边界intsum;};inta[N];Nodet[4*N];//更新线段树voidupdate(inti){t.sum=t[2*i].sum+t[2*i+1].sum;}//构建线段树voidbuild(inti,intl,intr){t.l=l;t.r=r;if(l==r){t.sum=a[l];return;}intm=(l+r)1;build(2*i,l,m);//左儿子build(2*i+1,m+1,r);//右儿子update(i);}inlinevoidupdate(inti,intdis,intk){if(t.l==t.r){//如果是叶子节点，找到了，回溯t.sum+=k;return;}if(dis=t[2*i].r){update(2*i,dis,k);//向左}else{update(2*i+1,dis,k);//向右}t.sum=t[i*2].sum+t[i*2+1].sum;//回溯更新}inlineintquery(inti,intl,intr){if(t.l=lt.r=r){//对应上面第一步returnt.sum;}if(t.lr
t.rl){//目标区间和当前区间没关系return0;}ints=0;//如果有关系，但是并不是完全包含if(t[i*2].r=l){//左儿子与目标区间相交s+=query(i*2,l,r);}if(t[i*2+1].l=r){//右儿子与目标区间相交s+=query(i*2+1,l,r);}returns;}intmain(){intn,m;cinnm;for(inti=1;i=n;i++){cina;}build(1,1,n);//先构建和后构建是有区别的for(inti=1;i=m;i++){intopt;cinopt;if(opt==1){intx,y;cinxy;update(1,x,y);}else{intx,y;cinxy;coutquery(1,x,y);}}return0;}
时间复杂度：
树的高度为O(logN)，每次查询肯定不超过4个节点，也就是最大4个，那么总的时间复杂度为O(4*logN)
②：区间修改，单点查询
如果把这个区间加上k，相当于把这个区间涂上一个k的标记，然后单点查询的时候，就从上跑到下，把沿路的标记加起来。
第一步：如果目标区间完全包含当前区间，将这个区间标记k
第二步：如果当前区间的左儿子和目标区间有交集，那么搜索当前区间左儿子
第三步：如果当前区间的右儿子和目标区间有交集，那么搜索当前区间右儿子
区间修改：
区间1~3都加k
inlinevoidupdate(inti,intl,intr,intk){if(tree.l=ltree.r=r){//区间所有权值加ktree.sum+=k;return;}if(tree[i*2].r=l){update(i*2,l,r,k);}if(tree[i*2+1].l=r){update(i*2+1,r,k);}}
单点查询：
intans=0;voidquery(inti,intdis){ans+=tree.sum;if(tree.l==tree.r){return;//递归边界}if(dis=tree[i*2].r){query(i*2,dis);}if(dis=tree[i*2+1].l){query(i*2+1,dis);}}
程序代码：
#includeiostreamusingnamespacestd;constintN=5e5+5;//线段树元素structNode{intl,r;//当前节点的区间边界intsum;};inta[N];Nodet[4*N];//更新线段树voidupdate(inti){t.sum=t[2*i].sum+t[2*i+1].sum;}//构建线段树voidbuild(inti,intl,intr){t.l=l;t.r=r;if(l==r){t.sum=a[l];return;}intm=(l+r)1;build(2*i,l,m);//左儿子build(2*i+1,m+1,r);//右儿子update(i);}inlinevoidupdate(inti,intl,intr,intk){if(t.l=lt.r=r){//区间所有权值加kt.sum+=k;//从下向上更新的值，最开始这里面全是0，更新哪个就会对整体产生影响return;}if(t[i*2].r=l){update(i*2,l,r,k);}if(t[i*2+1].l=r){update(i*2+1,l,r,k);}}intans=0;voidquery(inti,intdis){ans+=t.sum;//sum里面存储的都是变化值，把dis以下的所有累加起来就可以couti"----"t.sum"---";if(t.l==t.r){return;//递归边界}if(dis=t[i*2].r){query(i*2,dis);}if(dis=t[i*2+1].l){query(i*2+1,dis);}}intmain(){intn,m;cinnm;build(1,1,n);for(inti=1;i=n;i++){cina;}for(inti=1;i=m;i++){intopt;cinopt;if(opt==1){intx,y,z;cinxyz;update(1,x,y,z);}if(opt==2){ans=0;intx;cinx;query(1,x);coutans+a[x]endl;}}return0;}
③：区间修改，区间查询
如果要对[l，r]这个区间进行修改，需要对这个区间里面的所有节点遍历一遍，修改一次，时间复杂度高。
对于单点查询，区间修改后，我们可以使用递归从上往下把增量相加后再加上原数组的值，所以总体上没有影响。
但是对于区间查询，比如，1~4区间，如果把1~3区间都加1，相当于把节点1~2和节点3进行标记，等查询2~4区间时会发现，虽然1~2区间被标记，但是这个标记并没有pushdown（下推），导致区间查询时出现错误。
如果要查的2节点在1~2区间里面，我们可以把加1操作也推下来，那样就不会造成结果错误。
引入一个概念---懒惰标记(lazytag)
区间修改只需要通过先改变叶子节点的值，然后不断地向上递归修改父节点直至达到根节点，时间复杂度为O(n*logn)，引入懒惰标记后，时间复杂度降到了O(logn)级别。
[1,4]区间每个数加上，从根节点出发，找到[1,4]这个区间或其子区间，然后标记这个区间的每个数都加上，直接返回。不需要遍历这个子区间到每个叶子节点并对其分别加。
懒标记：标记的区间被更新过了，但是其子区间却没有被更新。
懒标记下推：
①：标记了[1,4]，没有标记子区间，查询[2,4]的区间和，需要下推懒标记
②：下推标记就是把一个节点的懒标记传给其左右儿子，再删除自己的标记
懒标记使用原则及步骤：
①：如果目标区间完全包含当前区间，将这个区间的每个数都加上修改增量k
tree.sum+k*(tree.r-tree.l+1)
②：如果没有完全包含，则先下传懒标记
③：如果这个区间的左儿子和目标区间有交集，那么搜索左儿子
④：如果这个区间的右儿子和目标区间有交集，那么搜索右儿子
⑤：回溯tree.sum=tree[i*2].sum+tree[i*2+1].sum
区间修改：
初始化状态：
第一次：对区间[1,4]进行标记+1操作,目标完全包含当前区间标记
第二次：对区间[3,5]进行标记+2操作
①：当i==2时，目标区间没有完全包含当前区间，懒标记下推
②：i==5
i==3,目标区间完全包含当前区间
voidupdate(inti,intl,intr,intk){//步骤一：完全包含if(tree.r=rtree.l=l){tree.sum+=k*(tree.r-tree.l+1);//记录懒标记tree.lz+=k;return;}//步骤二：没有完全包含push_down(i);//向下传递//步骤三：搜索左儿子if(tree[i*2].r=l){update(i*2,l,r,k);}//步骤四：搜索右儿子if(tree[i*2+1].l=r){update(i*2+1,l,r,k);}//步骤五：回溯tree.sum=tree[i*2].sum+tree[i*2+1].sum;return;}
懒标记下推：
voidpush_down(inti){if(tree.lz!=0){tree[i*2].lz+=tree.lz;//左儿子加上懒惰标记tree[i*2+1].lz+=tree.lz;//右儿子加上懒惰标记intmid=(tree.l+tree.r)/2;//左儿子更新sumtree[i*2].sum+=tree.lz*(mid-tree[i*2].l+1);//右儿子更新sumtree[i*2+1].sum+=tree.lz*(tree[i*2+1].r-mid);//父节点，删除本身标记tree.lz=0;}return;}
区间查询：
inlineintquery(inti,intl,intr){if(tree.l=ltree.r=r){returntree.sum;}if(tree.rl
tree.lr){return0;}push_down(i);//通过懒标记解决没有及时更新的问题ints=0;if(tree[i*2].r=l){s+=query(i*2,l,r);}if(tree[i*2+1].l=r){s+=query(i*2+1,l,r);}returns;}
程序代码：
#includeiostreamusingnamespacestd;constintN=5e5+5;//线段树元素structNode{intl,r,lz;//当前节点的区间边界intsum;};inta[N];Nodet[4*N];//更新线段树voidupdate(inti){t.sum=t[2*i].sum+t[2*i+1].sum;}//构建线段树voidbuild(inti,intl,intr){t.l=l;t.r=r;if(l==r){t.sum=a[l];return;}intm=(l+r)1;build(2*i,l,m);//左儿子build(2*i+1,m+1,r);//右儿子update(i);}voidpush_down(inti){if(t.lz!=0){t[i*2].lz+=t.lz;//左儿子加上懒惰标记t[i*2+1].lz+=t.lz;//右儿子加上懒惰标记intmid=(t.l+t.r)/2;//左儿子更新sumt[i*2].sum+=t.lz*(mid-t[i*2].l+1);//右儿子更新sumt[i*2+1].sum+=t.lz*(t[i*2+1].r-mid);//父节点，删除本身标记t.lz=0;}return;}voidupdate(inti,intl,intr,intk){//步骤一：完全包含if(t.r=rt.l=l){t.sum+=k*(t.r-t.l+1);//记录懒标记t.lz+=k;return;}//步骤二：没有完全包含push_down(i);//向下传递//步骤三：搜索左儿子if(t[i*2].r=l){update(i*2,l,r,k);}//步骤四：搜索右儿子if(t[i*2+1].l=r){update(i*2+1,l,r,k);}//步骤五：回溯t.sum=t[i*2].sum+t[i*2+1].sum;return;}inlineintquery(inti,intl,intr){if(t.l=lt.r=r){returnt.sum;}if(t.rl
t.lr){return0;}push_down(i);//通过懒标记解决没有及时更新的问题ints=0;if(t[i*2].r=l){s+=query(i*2,l,r);}if(t[i*2+1].l=r){s+=query(i*2+1,l,r);}returns;}intmain(){intn,m,opt,x,y,k;cinnm;for(inti=1;i=n;i++){cina;}build(1,1,n);for(inti=1;i=m;i++){cinoptxy;if(opt==1){cink;update(1,x,y,k);}else{coutquery(1,x,y)endl;}}return0;}
结果测试：
P
一只小跃跃