C语言-线段树

线段树讲解（数据结构、C++）声明：仅⼀张图⽚转载于，⾃⼰画太⿇烦了。

那个博客的讲解也很好，只是他⽤了指针的⽅式来定义线段树，⽽我⽤了结构体，并且他讲了线段树的更⾼级的操作，若对线段树的初级操作不理解，请继续阅读线段树作为⼀种⼗分常⽤的数据结构，在NOIP、NOI中⼴泛的出现，所以在这⾥对线段树进⾏简单的讲解。

线段树⽀持对⼀个数列的求和、单点修改、求最值（最⼤、最⼩）、区间修改（需要lazy标记，暂不讲解）。

这⼏种操作，时间复杂度是（logn）级别的，是⼀种⼗分优秀的数据结构。

因此其获得了⼴泛的应⽤。

定义：顾名思义，它是⼀种树形结构，但每段不是平常所学的⼀个点⼀个点的树，⽽是⼀条⼀条的线段，每条线段包含着⼀些值，其中最主要的是起始和结束点记作 l，r 即左端点和右端点。

那么该如何划分线段树呢？我们采⽤⼆分的思想，即每次将⼀段取半，再进⾏接下来的操作，这样综合了操作的⽅便程度和时间复杂度。

因为线段树通过⼆分得来，所以线段树是⼀颗⼆叉树。

这也⽅便了对⼉⼦查找。

下⾯是线段树的图，有利于理解：建树：仅仅知道模型还是不够的，建树的过程是线段树的关键（build(1,1,n)）从⼀号开始，左端是1，右端是n位运算 i<<1 等效于 i/2 (i<<1)|1 等效于 i/2+1 加速。

inline void update(int i)更新i节点维护的值（求和，最⼤……）{node[i].sum=node[i<<1].sum+node[(i<<1)|1].sum;node[i].maxx=max(node[i<<1].maxx,node[(i<<1)|1].maxx);}inline void build(int i,int l,int r)//inline 还是加速{node[i].l=l;node[i].r=r;//左右端点为当前递归到的 l 和 rif(l==r){//若l==r 则当前的树节点是真正意义上的点node[i].maxx=a[l];//最⼤值就是本⾝的值node[i].sum=a[l];//区间的和就是本⾝的值return;}int mid=(l+r)/2;//因为是⼆叉树所以以中点为分割点build(i<<1,l,mid);//根据⼆叉树的知识，左⼉⼦是i/2右⼉⼦是i/2+1build((i<<1)|1,mid+1,r);update(i);}数列求和：这是线段树的⼀个典型算法，其他的很多应⽤都是从中转化的。

线段树转载请注明出处，谢谢！/metalseed/article/details/8039326持续更新中···一：线段树基本概念1：概述线段树，类似区间树，是一个完全二叉树，它在各个节点保存一条线段（数组中的一段子数组），主要用于高效解决连续区间的动态查询问题，由于二叉结构的特性，它基本能保持每个操作的复杂度为O(lgN)!性质：父亲的区间是[a,b],(c=(a+b)/2)左儿子的区间是[a,c]，右儿子的区间是[c+1,b]，线段树需要的空间为数组大小的四倍2：基本操作（demo用的是查询区间最小值）线段树的主要操作有：(1)：线段树的构造void build(int node, int begin, int end);主要思想是递归构造，如果当前节点记录的区间只有一个值，则直接赋值，否则递归构造左右子树，最后回溯的时候给当前节点赋值1.#include <iostream>ing namespace std;3.4.const int maxind = 256;5.int segTree[maxind * 4 + 10];6.int array[maxind];7./* 构造函数，得到线段树 */8.void build(int node, int begin, int end)9.{10. if (begin == end)11. segTree[node] = array[begin]; /* 只有一个元素,节点记录该单元素 */12. else13. {14. /* 递归构造左右子树 */15. build(2*node, begin, (begin+end)/2);16. build(2*node+1, (begin+end)/2+1, end);17.18. /* 回溯时得到当前node节点的线段信息 */19. if (segTree[2 * node] <= segTree[2 * node + 1])20. segTree[node] = segTree[2 * node];21. else22. segTree[node] = segTree[2 * node + 1];23. }24.}25.26.int main()27.{28. array[0] = 1, array[1] = 2,array[2] = 2, array[3] = 4, array[4] = 1, array[5] = 3;29. build(1, 0, 5);30. for(int i = 1; i<=20; ++i)31. cout<< "seg"<< i << "=" <<segTree[i] <<endl;32. return 0;33.}此build构造成的树如图：(2)：区间查询int query(int node, int begin, int end, int left, int right);（其中node为当前查询节点，begin,end为当前节点存储的区间，left,right为此次query所要查询的区间）主要思想是把所要查询的区间[a,b]划分为线段树上的节点，然后将这些节点代表的区间合并起来得到所需信息比如前面一个图中所示的树，如果询问区间是[0,2]，或者询问的区间是[3,3]，不难直接找到对应的节点回答这一问题。

线段树五种基本操作代码模板这个模板是从⼤神：的博客上摘抄过来的注意：⼀开始要定义全局变量，n是节点数，m是操作数，查询操作都是void型的，所以需要有ans来承载答案，每个操作初始都要把ans置0，a,b是左右区间，p,a,b是输⼊模板⾥的区间修改和单点修改都是值加上⼀个数，如果是变成⼀个数把函数⾥的+=改成=就好另外找到⼀个模板好像⽐较好，先码住吧。

题⽬链接：#include<bits/stdc++.h>using namespace std;string s;int dat[4000005],lazy[4000005],a[4000005];int n;void pushup(int rt){dat[rt]=dat[2*rt]+dat[2*rt+1];};void build(int l,int r,int rt){if (l==r-1){dat[rt]=a[l];return;}int mid=(l+r)>>1;build(l,mid,rt<<1);build(mid,r,rt<<1|1);pushup(rt);}void pushdown(int rt,int l,int r){if (lazy[rt]!=-1){lazy[2*rt]=lazy[2*rt+1]=lazy[rt];dat[2*rt+1]=dat[2*rt]=lazy[rt]*(r-l)/2;lazy[rt]=-1;}}void update(int L,int R,int l,int r,int rt,int c){if (L<=l&&r<=R){dat[rt]=c*(r-l);lazy[rt]=c;return;}int mid=(l+r)>>1;pushdown(rt,l,r);if (L<mid) update(L,R,l,mid,rt<<1,c);if (R>mid) update(L,R,mid,r,rt<<1|1,c);pushup(rt);}//更新pushup pushdown都需要int query(int L,int R,int l,int r,int rt){if (L<=l&&r<=R)return dat[rt];int mid=(l+r)>>1;pushdown(rt,l,r);//若更新只有点更新，不需要这句int ANS=0;if (L<mid) ANS+=query(L,R,l,mid,rt<<1);if (R>mid) ANS+=query(L,R,mid,r,rt<<1|1);return ANS;}//查询只需要pushdownint main(){cin>>s;int n_=s.size();for(int i=1;i<=n_;i++)a[i]=s[i-1]-'0';n=1;while(n<n_)n*=2;build(1,n+1,1);memset(lazy,-1,sizeof(lazy));int m;scanf("%d",&m);for(int i=1;i<=m;i++){int l,r,flag;scanf("%d %d %d",&l,&r,&flag);int t=query(l,r+1,1,1+n,1);if(flag==0){update(l,r+1-t,1,1+n,1,0);update(r-t+1,r+1,1,1+n,1,1);}else{update(l,l+t,1,1+n,1,1);update(l+t,r+1,1,1+n,1,0);}}for(int i=1;i<=n_;i++)printf("%d",query(i,i+1,1,1+n,1));}这个是之前的模板#include<cstdio>using namespace std;int n,p,a,b,m,x,y,ans;struct node{int l,r,w,f;}tree[400001];inline void build(int k,int ll,int rr)//建树{tree[k].l=ll,tree[k].r=rr;if(tree[k].l==tree[k].r){scanf("%d",&tree[k].w);return;}int m=(ll+rr)/2;build(k*2,ll,m);build(k*2+1,m+1,rr);tree[k].w=tree[k*2].w+tree[k*2+1].w;}inline void down(int k)//标记下传{tree[k*2].f+=tree[k].f;tree[k*2+1].f+=tree[k].f;tree[k*2].w+=tree[k].f*(tree[k*2].r-tree[k*2].l+1);tree[k*2+1].w+=tree[k].f*(tree[k*2+1].r-tree[k*2+1].l+1); tree[k].f=0;}inline void ask_point(int k)//单点查询{if(tree[k].l==tree[k].r){ans=tree[k].w;return ;}if(tree[k].f) down(k);int m=(tree[k].l+tree[k].r)/2;if(x<=m) ask_point(k*2);else ask_point(k*2+1);}inline void change_point(int k)//单点修改{if(tree[k].l==tree[k].r){tree[k].w+=y;return;}if(tree[k].f) down(k);int m=(tree[k].l+tree[k].r)/2;if(x<=m) change_point(k*2);else change_point(k*2+1);tree[k].w=tree[k*2].w+tree[k*2+1].w;}inline void ask_interval(int k)//区间查询{if(tree[k].l>=a&&tree[k].r<=b){ans+=tree[k].w;return;}if(tree[k].f) down(k);int m=(tree[k].l+tree[k].r)/2;if(a<=m) ask_interval(k*2);if(b>m) ask_interval(k*2+1);}inline void change_interval(int k)//区间修改{if(tree[k].l>=a&&tree[k].r<=b){tree[k].w+=(tree[k].r-tree[k].l+1)*y;tree[k].f+=y;return;}if(tree[k].f) down(k);int m=(tree[k].l+tree[k].r)/2;if(a<=m) change_interval(k*2);if(b>m) change_interval(k*2+1);tree[k].w=tree[k*2].w+tree[k*2+1].w;}int main(){scanf("%d",&n);//n个节点build(1,1,n);//建树scanf("%d",&m);//m种操作for(int i=1;i<=m;i++){scanf("%d",&p);ans=0;if(p==1){scanf("%d",&x);ask_point(1);//单点查询,输出第x个数printf("%d",ans);}else if(p==2){scanf("%d%d",&x,&y);change_point(1);//单点修改}else if(p==3){scanf("%d%d",&a,&b);//区间查询ask_interval(1);printf("%d\n",ans);}else{scanf("%d%d%d",&a,&b,&y);//区间修改 change_interval(1);}}}。

线段树目录定义基本结构实现代码树状数组编辑本段定义区间在[1,5]内的线段树线段树又称区间树，是一种对动态集合进行维护的二叉搜索树，该集合中的每个元素 x 都包含一个区间 Interval [ x ]。

线段树支持下列操作：Insert(t,x)：将包含区间 int 的元素 x 插入到树中；Delete(t,x)：从线段树 t 中删除元素 x；Search(t,i)：返回一个指向树 t 中元素 x 的指针。

编辑本段基本结构线段树是建立在线段的基础上，每个结点都代表了一条线段[a , b]。

长度为1的线段称为元线段。

非元线段都有两个子结点，左结点代表的线段为[a , (a + b ) / 2]，右结点代表的线段为[( a + b ) / 2 , b]。

右图就是一棵长度范围为[1 , 5]的线段树。

长度范围为[1 , L] 的一棵线段树的深度为log ( L - 1 ) + 1。

这个显然，而且存储一棵线段树的空间复杂度为O(L)。

线段树支持最基本的操作为插入和删除一条线段。

下面以插入为例，详细叙述，删除类似。

将一条线段[a , b] 插入到代表线段[l , r]的结点p中，如果p不是元线段，那么令mid＝（l＋r）/2。

如果b<mid，那么将线段[a , b] 也插入到p的左儿子结点中，如果a>mid，那么将线段[a , b] 也插入到p的右儿子结点中。

插入（删除）操作的时间复杂度为O (Log N)。

上面的都是些基本的线段树结构，但只有这些并不能做什么，就好比一个程序有输入没输出，根本没有任何用处。

最简单的应用就是记录线段有否被覆盖，并随时查询当前被覆盖线段的总长度。

那么此时可以在结点结构中加入一个变量int count；代表当前结点代表的子树中被覆盖的线段长度和。

这样就要在插入（删除）当中维护这个count值，于是当前的覆盖总值就是根节点的count值了。

另外也可以将count换成bool cover；支持查找一个结点或线段是否被覆盖。

线段树详解及例题一、线段树的概念线段树（Segment Tree）是一种用于解决区间查询问题的数据结构，常用于静态区间查询和动态区间查询，也被称为区间树。

二、线段树的构建线段树是一棵二叉树，其每个节点都代表一个区间。

首先，我们将待处理的区间按照二叉树的方式进行划分，生成一棵满二叉树。

这里我们以求一段区间内元素的和为例：（1）首先，将整个区间 $[1,n]$ 分为两个部分，设左边区间为$[1,mid]$，右边区间为 $[mid+1,n]$。

这里的 $mid$ 是 $(1+n)/2$ 的值。

（2）然后，将左区间和右区间再分别划分成两个子区间并进行相加，直到区间大小为 1，构建出一棵完整的线段树。

三、线段树的维护构建好线段树之后，我们需要对其进行维护，以便能够快速地查询给定区间的值。

设线段树中某个节点代表区间 $[l,r]$，那么这个节点的值等于 $[l,r]$ 区间中所有元素的和。

如果需要对线段树进行更新，我们可以利用递归的方式向下更新每个节点的值。

当需要将 $[l,r]$ 区间中的某个元素修改为 $x$ 时，我们可以将其视为将线段树上区间 $[l,r]$ 的值都减去原来元素的值再加上 $x$。

四、线段树的查询线段树的查询包括单点查询和区间查询两种方式：（1）单点查询：即查询线段树中某个节点所代表的区间的值。

（2）区间查询：即查询线段树中 $[l,r]$ 区间内所有元素的和。

五、应用实例下面通过几道例题来说明线段树的应用。

问题一：给定一个序列，更新其中某个元素的值，并求出其区间和。

样例输入：8 1 3 -4 2 8 10 9 62 5 2样例输出：17问题二：对一个序列进行 $m$ 次操作，每次操作为在 $L$ 到 $R$ 的区间内加上 $c$，并输出最终改变后的序列。

样例输入：5 31 3 23 5 32 4 1样例输出：2 5 4 0 2以上就是关于线段树的详细介绍和几个应用示例，希望可以对读者有所帮助。

线段树（lazy标记）1 # include<cstdio>2 # include<iostream>34using namespace std;56 # define MAX 1000047 # define lid id<<18 # define rid id<<1|1910 typedef long long LL;11int n;1213struct Segtree14 {15int l,r;16 LL lazy,sum;17 inline int len()18 {19return r-l+1;20 }21 }tree[MAX*4];2223int a[MAX];2425void push_up( int id )26 {27 tree[id].sum = tree[rid].sum+tree[lid].sum;28 }2930void push_down( int id )31 {32if ( tree[id].lazy==0 )33return;34 tree[lid].lazy += tree[id].lazy;35 tree[rid].lazy += tree[id].lazy;36 tree[lid].sum += tree[id].lazy*tree[lid].len();37 tree[rid].sum += tree[id].lazy*tree[rid].len();38 tree[id].lazy = 0;39 }4041void build( int id,int l,int r )42 {43 tree[id].l = l; tree[id].r = r;44if ( l==r )45 {46 tree[id].sum = a[l];47return;48 }49int mid = (tree[id].l+tree[id].r)/2;50 build(lid,l,mid);51 build(rid,mid+1,r);52 push_up(id);53 }5455void update( int id,int l,int r,int val )56 {57if ( tree[id].l==l&&tree[id].r==r )58 {59 tree[id].lazy += val;60 tree[id].sum += 1LL*val*tree[id].len();61return;62 }63 push_down(id);64int mid = ( tree[id].l+tree[id].r )/2;65if ( r <= mid )66 update(lid,l,r,val);67else if ( l > mid )68 update(rid,l,r,val);69else70 {71 update(lid,l,mid,val);72 update(rid,mid+1,r,val);73 }74 push_up(id);75 }7677 LL query( int id,int l,int r )78 {79if ( tree[id].l==l&&tree[id].r==r )80 {81return tree[id].sum;82 }83 push_down(id);84int mid = ( tree[id].l+tree[id].r )/2;85if ( r <= mid )86return query(lid,l,r);87else if ( l > mid )88return query(rid,l,r);89else90return query(lid,l,mid)+query(rid,mid+1,r); 91 }9293int main(void)94 {95while ( scanf("%d",&n)!=EOF )96 {97for ( int i = 1;i <= n;i++ )98 {99 scanf("%d",&a[i]);100 }101 build(1,1,n);102int q; scanf("%d",&q);103while( q-- )104 {105int ll,rr,t3; scanf("%d%d%d",&ll,&rr,&t3); 106 update(1,ll,rr,t3);107 LL ans = query(1,ll,rr);108 printf("%lld\n",ans);109 }110 }111112return0;113 }。

树状数组和线段树-电脑资料一、树状数组在解题过程中，我们有时需要维护一个数组的前缀和S[i]=A[1]+A[2]+...+A[i]，实现：对于正整数x，定义lowbit（x）为x的二进制表达式中最右边的1所对应的值。

Lowbit(x)=xand-x对于节点i，如果它是左子节点，其父节点为i+lowbit(i)；构造一个辅助数组C，其中Ci=Ai-lowbit(i)+1+Ai-lowbit(i)+2+…+Ai即C的每个元素都是A数组中的一段连续和。

具体是每个灰色节点i都属于一个以它自身结尾的水平长条，这个长条中的数之和就是Ci。

如C12=A9+A10+A11+A12=C10+A11+A12如何更新C数组中的元素：如果修改了一个Ai，需要更新C数组中的哪些元素呢？从Ci开始往右走，边走边“往上爬”（不一定沿着树中的边爬），沿途修改所有结点对应的Ci即可。

预处理时先把C数组清空，然后执行n次add操作。

总时间为O（nlogn）如何计算前缀和Si：顺着结点i往左走，边走边“往上爬”（不一定沿着树中的边爬），把沿途经过的Ci累加起来就可以了。

对于query（L,R）=SR-SL-1。

代码：varb,c,f:array[0..100000]oflongint;ff,a:Array[0..100000]ofboolean; i,j,m,n,x,y,ans,l,r,tmp:longint; s:string;functiondfs(x:longint):longint; beginifx<=1thenexit;c[f[x]]:=c[f[x]]+c[x];dfs(f[x]);end;proceduredfs1(x:longint);begindec(c[x]);ifx<=1thenexit;dfs1(f[x]);end;proceduredfs2(x:longint);begininc(c[x]);ifx<=1thenexit;dfs2(f[x]);beginreadln(n);fillchar(ff,sizeof(ff),true); fori:=1ton-1dobeginreadln(x,y);f[y]:=x;inc(b[x]);end;fori:=1tondoc[i]:=1;fori:=1tondobeginifb[i]=0thendfs(i);end;readln(m);fori:=1tomdobeginx:=0;readln(s);ifs[1]='Q'thenforj:=3tolength(s)dox:=x*10+ord(s[j])-ord('0');writeln(c[x]);end;ifs[1]='C'thenbeginforj:=3tolength(s)dox:=x*10+ord(s[j])-ord('0');ifff[x]thendfs1(x)elsedfs2(x);ff[x]:=notff[x];end;end;End.二、线段树1,.线段树的结构:区间：用一对数a和b表示一个前闭后开的区间[a,b)。

线段树入门OI中经常能碰见统计类型的题目。

要求出某些时刻、某种情况下，状态是怎样的。

这类问题往往比较简单明了，也能十分容易地写出模拟程序。

但较大的数据规模使得模拟往往不能满足要求。

一、线段树的结构：线段树是一棵二叉树，其结点是一条“线段”——[a,b]，它的左儿子和右儿子分别是这条线段的左半段和右半段，即[a, (a+b)/2]和[(a+b)/2,b]。

线段树的叶子结点是长度为1的单位线段[a,a+1]。

下图就是一棵根为[1,10]的线段树：【1,10】/ \【1,5】【5,10】 / \/ \【1,3】【3,5】【5,7】【7,10】/ \ / \ /\ / \【1,2】【2,3】【3,4】【4,5】【5,6】【6,7】【7,8】【8,10】 / \【8,9】【9,10】易证一棵以[a,b]为根的线段树结点数是2*(b-a)-1。

由于线段树是一棵平衡二叉树，因此一棵以[a,b]为根的线段树的深度为log2(2*(b-a))。

一般采用静态完全二叉树来表示线段树。

（但有时有一些缺点）struct segtree{int a,b,left,right;};其中分别表示线段的左端点和右端点，Left，Right 表示左儿子和右儿子的编号。

因此我们可以用一个一维数组来表示一棵线段树：segtree tree[MaxN];根据实际需要，我们可以增加其它的域，例如cover域来计算该线段被覆盖的次数，或是其它一些形式的域。

二、建立线段树：void build(int step, int s, int t){a[step].a = s;a[step].b = t;a[step].cn = 0;if (t-s>1){int mid=(s+t)/2;build(step*2, s, mid);build(step*2+1, mid, t);}}建立以step为根结点，范围从s到t的线段树。

这里应用了完全二叉树的特点：step 的左孩子结点编号为2*step，右孩子结点编号为2*step+1。

线段树之区间最⼤数（线段树⼊门）线段树初级（区间最⼤数）其实就是对树进⾏⼆分查找（当然需要结合递归）思路：要从区间中找到最⼤数，当然可以暴⼒求解，但你不怕超时吗so 让我们来学习线段树吧#include <iostream>#include <cstdio>#include <cstring>using namespace std;#define maxn 100010struct N{int l, r, max;} tree[maxn * 4]; //注意乘三int num[maxn];void build(int node, int l, int r){tree[node].l = l;tree[node].r = r;if(l == r){scanf("%d", &tree[node].max);return;}int mid = (l + r) / 2;build(node * 2, l, mid);build(node * 2 + 1, mid + 1, r);tree[node].max = max(tree[node << 1].max, tree[node << 1 | 1].max);return;}int query(int node, int ql, int qr){int l = tree[node].l;int r = tree[node].r;if(l == ql && r == qr)return tree[node].max;//if (l == r) return tree[node].max;int mid = (l + r) / 2;if(qr <= mid)return query(node << 1, ql, qr);else if(ql > mid)return query(node << 1 | 1, ql, qr);elsereturn max(query(node << 1, ql, mid), query(node << 1 | 1, mid + 1, qr));}int main(){int n, m;int ql, qr;scanf("%d %d", &n, &m);build(1, 1, n);for(int i = 0; i < m; i++){scanf("%d %d", &ql, &qr);printf("%d\n", query(1, ql, qr));}}题⽬描述给出⼀列数共N个，将其从1到N编号，进⾏M次查询[X, Y](X<=Y)，给出第X个数到第Y个数间最⼤的数。

p1047线段树写法以下是P1047校门外的树这道题目的线段树写法示例代码：c复制代码#include <iostream>#include <cstdio>using namespace std;const int maxn = 10010;int sum[maxn << 2], lazy[maxn << 2];void pushup(int rt) {sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];}void build(int l, int r, int rt) {lazy[rt] = 0;if (l == r) {sum[rt] = 1;return;}int m = (l + r) >> 1;build(l, m, rt << 1);build(m + 1, r, rt << 1 | 1);pushup(rt);}void update(int L, int R, int l, int r, int rt) {if (L <= l && r <= R) {sum[rt] = 0;lazy[rt] = 1;return;}if (lazy[rt]) {sum[rt << 1] = 0;sum[rt << 1 | 1] = 0;lazy[rt << 1] = 1;lazy[rt << 1 | 1] = 1;lazy[rt] = 0;}int m = (l + r) >> 1;if (L <= m) update(L, R, l, m, rt << 1);if (R > m) update(L, R, m + 1, r, rt << 1 | 1);pushup(rt);}int main() {int L, M;cin >> L >> M;build(0, L, 1);for (int i = 0; i < M; i++) {int a, b;cin >> a >> b;update(a, b, 0, L, 1);}cout << sum[1] << endl;return 0;}在这个代码中，我们定义了一个sum数组和一个lazy数组，分别表示每个区间的树的数量和延迟标记。

【数据结构】线段树的⼏种⽤法区间修改与区间查询运⽤Lazy-Tag（懒标记）的维护⽅法例题：代码：#include<iostream>#include<cstdio>#include<cstring>using namespace std;#define maxn 100007#define ll long longll sum[maxn<<2],add[maxn<<2],a[maxn],n,m;void build(ll l,ll r,ll k)//建树 [l,r]中编号为k的区间{if(l==r)//叶⼦节点{sum[k]=a[l];return;}ll mid=(l+r)>>1;build(l,mid,k<<1);//左⼦树build(mid+1,r,k<<1|1);//右⼦树sum[k]=sum[k<<1]+sum[k<<1|1];//更新区间和}void Add(ll l,ll r,ll v,ll k)//给定区间[l,r]中所有的数加上v{add[k]+=v;//打标记sum[k]+=(r-l+1)*v;//维护对应区间和return;}void pushdown(ll l,ll r,ll mid,ll k)//标记下传{if(add[k]==0) return;//如果没有标记就退出Add(l,mid,add[k],k<<1);//传给左⼦树Add(mid+1,r,add[k],k<<1|1);//传给右⼦树add[k]=0;//传完之后清楚标记}void update(ll x,ll y,ll v,ll l,ll r,ll k)//更新定区间[x,y]中区间[l,r]第k个区间{if(l>=x&&r<=y) return Add(l,r,v,k);//当这个定区间包含区间[l,r] 则更新区间[l,r]的值ll mid=(l+r)>>1;pushdown(l,r,mid,k);//标记下传if(x<=mid) update(x,y,v,l,mid,k<<1);//更新左⼦树if(mid<y) update(x,y,v,mid+1,r,k<<1|1);//更新右⼦树sum[k]=sum[k<<1]+sum[k<<1|1];//更新下传后当前正确的sum值}ll query(ll x,ll y,ll l,ll r,ll k)//查询定区间[x,y]中区间[l,r]第k个区间{if(l>=x&&r<=y) return sum[k];//当这个定区间包含区间[l,r] 返回区间[l,r]的值ll mid=(l+r)>>1;ll res=0;pushdown(l,r,mid,k);//标记下传if(x<=mid) res+=query(x,y,l,mid,k<<1);//如果左⼦树还有值就加上左⼦树if(y>mid) res+=query(x,y,mid+1,r,k<<1|1);//同上右⼦树return res;//返回值}int main(){cin>>n>>m;for(ll i=1;i<=n;i++) cin>>a[i];build(1,n,1);//建原树for(ll i=1;i<=m;i++){ll x,y,z;cin>>x;if(x==1){cin>>x>>y>>z;update(x,y,z,1,n,1);//更新值}else{cin>>x>>y;cout<<query(x,y,1,n,1)<<endl;//查询区间}}}例题：代码：#include<iostream>#include<cstdio>#include<cstring>using namespace std;#define maxn 100007#define ll long longll sum[maxn<<2],add[maxn<<2],mul[maxn<<2],a[maxn],n,m,p;void build(ll l,ll r,ll k){mul[k]=1;//初始化标记if(l==r){sum[k]=a[l]%p;mul[k]=1;return;}ll mid=(l+r)>>1;build(l,mid,k<<1);//左右⼦树构建build(mid+1,r,k<<1|1);sum[k]=(sum[k<<1]+sum[k<<1|1])%p;//维护sum值}void pushdown(ll l,ll r,ll mid,ll k)//标记下放{//先乘后加if(mul[k]!=1)//当有乘法标记计算所有的值{sum[k<<1]=(sum[k<<1]*mul[k])%p;sum[k<<1|1]=(sum[k<<1|1]*mul[k])%p;mul[k<<1]=(mul[k<<1]*mul[k])%p;mul[k<<1|1]=(mul[k<<1|1]*mul[k])%p;add[k<<1]=(add[k<<1]*mul[k])%p;//加法标记也要乘add[k<<1|1]=(add[k<<1|1]*mul[k])%p;mul[k]=1;//清除标记}if(add[k])//当有加法标记{sum[k<<1]=(sum[k<<1]+add[k]*(mid-l+1)%p)%p;//左右⼦树计算右⼦树不⽤+1 sum[k<<1|1]=(sum[k<<1|1]+add[k]*(r-mid)%p)%p;//注意这⾥要先算sum 再算add add[k<<1]=(add[k]+add[k<<1])%p;//如果先算add 那再sum中的add值已经改变 add[k<<1|1]=(add[k]+add[k<<1|1])%p;//坑了我⼀个晚上（太弱了）add[k]=0;//清除标记}return;}void update1(ll x,ll y,ll v,ll l,ll r,ll k)//在定区间[x,y]加上v{if(l>=x&&r<=y)//如果整个区间包含{add[k]=(add[k]+v)%p;sum[k]=(sum[k]+(r-l+1)*v)%p;return;}ll mid=(l+r)>>1;pushdown(l,r,mid,k);if(x<=mid) update1(x,y,v,l,mid,k<<1);if(mid<y) update1(x,y,v,mid+1,r,k<<1|1);sum[k]=(sum[k<<1]+sum[k<<1|1])%p;//计算标记下放之后的值return;}void update2(ll x,ll y,ll v,ll l,ll r,ll k)//在定区间[x,y]乘上v{if(l>=x&&r<=y)//如果整个区间包含{mul[k]=(mul[k]*v)%p;add[k]=(add[k]*v)%p;sum[k]=(sum[k]*v)%p;return;}ll mid=(l+r)>>1;pushdown(l,r,mid,k);if(x<=mid) update2(x,y,v,l,mid,k<<1);if(mid<y) update2(x,y,v,mid+1,r,k<<1|1);sum[k]=(sum[k<<1]+sum[k<<1|1])%p;//计算标记下放之后的值return;}ll query(ll x,ll y,ll l,ll r,ll k){if(l>=x&&r<=y) return sum[k]%p;ll mid=(l+r)>>1;ll res=0;pushdown(l,r,mid,k);//标记下放if(x<=mid) res+=query(x,y,l,mid,k<<1); res%=p;if(y>mid) res+=query(x,y,mid+1,r,k<<1|1); return res%p;}int main(){cin>>n>>m>>p;for(ll i=1;i<=n;i++) cin>>a[i];build(1,n,1);for(ll i=1;i<=m;i++){ll x,y,z;cin>>x;if(x==1){cin>>x>>y>>z;update2(x,y,z,1,n,1);}else if(x==2){cin>>x>>y>>z;update1(x,y,z,1,n,1);}else if(x==3){cin>>x>>y;cout<<query(x,y,1,n,1)<<endl;}}}。

线段树（原理简述+C++代码）线段树简述线段树的特点：操作逻辑是树的逻辑（左右⼦节点概念）底层数据存储却是⽤数字实现的。

说⽩了，线段树对应的是⼀棵完全⼆叉树，每个节点在数组中的位置就是该该节点在层序遍历中的序号（从1开始）。

基于数组实现我们能⽅便的访问⼀个节点的左右⼦节点，设当前节点存储序号idx，则左右⼦节点为存储序号分别为idx*2和idx*2+1。

线段树有什么⽤?考虑⼀个场景，我们有⼀个数组ori[1:n]，在任意时刻我们希望把某区间ori[a:b]内的数据同时更新（加上某个数），或者是查询区间ori[a:b]内所有数字的和。

要实现这样⼀个功能，如果采⽤原始的实现的话，操作复杂度是O(b−a)，在区间较⼤时复杂度不可接受。

1. 优化查询复杂度，如果我们能把b−a拆分成为 2 的幂次的加和，并且存储了这些区间的信息，那么我们可以将这些区间的的加起来即为总和。

优化后复杂度为O(log2(n))。

2. 优化更新复杂度，引⼊⼀个 lazy 优化（需要额外的O(n) 空间），同样能把更新复杂度优化到O(log2(n))。

lazy ⽤⽽实现这两点刚好就可以⽤线段树来实现，线段树的每个节点包含的信息是某区间内的信息。

如下图在整个线段树的实现中，我们只有⼀个数组arr[]⽤来保存节点的值（某区间内数的和）。

原始数组ori[]已经被映射到了arr[]中，不再单独占⽤存储空间。

考虑查询sum(ori[3:7])，拆分可得sum(ori[3:7]) = sum(ori[3:4]) + sum(ori[5:6]) + sum(ori[7,7])，即访问arr[]的5,6,14号节点即可。

显然借助arr[]就可以实现log(N) 复杂度；更新时我们同样可以将区间拆分，同样考虑更新区间ori[3:7]，拆分为ori[3:4], ori[5:6], ori[7:7]，ori[3:4]对应arr[]的 5 号节点，更新到 5号节点后不在往下更新，映⼊⼀个 lazy 变量来缓存更新信息，待下次查询或者更新到 5 节点的⼦节点时再把该缓存信息更新到⼦节点。

线段树 导⼊概念：1>线段树的结构：线段树是⼀种⼆叉搜索树。

2>⽤途： 1.在线维护修改以及查询区间上的最值，求和。

2.扩充到⼆维线段树（矩阵树）和三维线段树（空间树）。

3>时间复杂度： 对于⼀维线段树来说，每次更新以及查询的时间复杂度为O(logN)。

线段树基本内容 对于A[1:6] = {1,8,6,4,3,5}来说，线段树如上所⽰，红⾊代表每个结点存储的区间，蓝⾊代表该区间最值。

可以发现，每个叶⼦结点的值就是数组的值，每个⾮叶⼦结点的度都为⼆，且左右两个孩⼦分别存储⽗亲⼀半的区间。

每个⽗亲的存储的值也就是两个孩⼦存储的值的最⼤值。

对于⼀个区间[l,r]来说，最重要的数据当然就是区间的左右端点l和r，但是⼤部分的情况我们并不会去存储这两个数值，⽽是通过递归的传参⽅式进⾏传递。

这种⽅式⽤指针好实现，定义两个左右⼦树递归即可，但是指针表⽰过于繁琐，⽽且不⽅便各种操作，⼤部分的线段树都是使⽤数组进⾏表⽰，那这⾥怎么快速使⽤下标找到左右⼦树呢。

对于上述线段树，我们增加绿⾊数字为每个结点的下标 注意：⽆优化的线段树建树需要2*2k（2k-1 < n < 2k)空间，⼀般会开到4*n的空间防⽌RE。

易知：1.每个左⼦树的下标都是偶数，右⼦树的下标都是奇数且为左⼦树下标+1 2. l= fa*2 3.r = fa*2+1 推论：以k为⽗节点的编号有：左⼦树编号为k<<1,右⼦树编号为k<<1|1; code：线段树的基本操作 1.点更新 更新⼀个⼦节点，则每个包含此值的结点都需要更新，于是我们可以⽤递归查找哪个⼦节点需要修改，在回溯的时候改变⽗节点的值。

code： 2.区间查询 我们可以将要查询的区间分配到个个节点中，在递归的同时判断所要查询的区间是否能够完全包含当前节点所代表的区间 1.完全包含,返回该节点上的值。

2.不完全包含，将该查询任务下发到左右⼦节点中。

菜鸟都能理解的线段树入门经典线段树的定义首先，线段树既是线段也是树，并且是一棵二叉树，每个结点是一条线段,每条线段的左右儿子线段分别是该线段的左半和右半区间，递归定义之后就是一棵线段树，图示如下图1.线段树示意图定义线段树的数据结构struct Line{int left, right, count;Line *leftChild, *rightChild;Line(int l, int r): left(l), right(r) {}};PS:其中的count字段表示该条线段有几条明白了线段树的定义之后，我们来举一个例子来说明线段树的应用例题：给定N条线段，{[2, 5], [4, 6], [0, 7]}, M个点{2, 4, 7},判断每个点分别在几条线段出现过看到题目，有的人第一感觉想出来的算法便是对于每一个点，逐个遍历每一条线段，很轻松地判断出来每个点在几条线段出现过，小学生都会的算法，时间复杂度为O(M*N)如国N非常大，比如2^32-1, M也非常大M = 2^32 - 1, O(M*N)的算法将是无法忍受的，这个时候，线段树便隆重登场了线段树的解法：1.首先，我们找出一个最大的区间能够覆盖所有的线段，遍历所有的线段，找线段的最值(左端点的最小值，右端点的最大值)便可以确定这个区间，对于{[2, 5], [4, 6], [0, 7]}, 这个区间为[0, 7]，时间复杂度为O(N)2.然后，根据此区间建一棵线段树(见图1), 时间复杂度为O(log(MAX-MIN))3.对于每一条线段A，从根节点开始遍历这棵线段树，对于每一个当前遍历的结点NODE(其实线段树中每一个结点就是一条线段)，考虑三种情况a)如果线段A包含在线段NODE的左半区间，那么从NODE的左儿子(其实就是NODE 的左半区间)开始遍历这棵树b)如果线段A包含在线段NODE的右半区间，那么从NODE的右儿子(其实就是NODE 的右半区间)开始遍历这棵树c)如果线段A刚好和线段NODE重合，停止遍历，并将NODE中的count字段加1d)除了以上的情况，就将线段A的左半部分在NODE的左儿子处遍历，将A的右半部分在NODE的右儿子处遍历补充说明：对于以上的步骤，所做的工作其实就是不断地分割每一条线段，使得分割后的每一条小线段刚好能够落在线段树上，举个例子，比如要分割[2, 5],首先将[2, 5]和[0, 7]比较，符合情况d, 将A分成[2, 3]与[4, 5]I)对于[2, 3]从[0, 7]的左半区间[0, 3]开始遍历将[2, 3]与[0, 3]比较，满足情况b,那么从[0, 3]的右半区间[2, 3]开始遍历,发现刚好重合，便将结点[2, 3]count字段加1II)对于[4, 5]从[0, 7]的右半区间[4, 7]开始遍历将[4, 5]与[4, 7]比较，满足情况b，从[4, 7]的左半区间[4, 5]开始遍历，发现刚好重合，便将结点[4, 5]count字段加1于是对于[2, 5]分割之后线段树的情况为图2图2.分割[2,5]之后线段树的情况显然，我们看到，上述的遍历操作起始就是将[2, 5]按照线段树中的线段来分割，分割后的[2, 3]与[4, 5]其实是与[2, 5]完全等效的最后，我们将剩下的两条线段按照同样的步骤进行分割之后，线段树的情况如下图3这一步的时间复杂度为O(N*log(MAX-MIN))4.最后，对于每一个值我们就可以开始遍历这一颗线段树，加上对于结点的count字段便是在线段中出现的次数比如对于4，首先遍历[0, 7]，次数= 0+1=1；4在右半区间，遍历[4, 7],次数= 1+0=0;4在[4, 7]左半区间, 次数= 1+2=3;4在[4, 5]左半区间,次数= 3+0 = 4，遍历结束，次数= 3说明4在三条线段中出现过,同理可求其他的值，这一步的时间复杂度为O(M*log(MAX-MIN))最后，总的时间复杂度为O(N)+O(log(MAX-MIN))+O(N*log(MAX-MIN))+(M*log(MAX-MIN)) = O((M+N)*log(MAX-MIN))由于log(MAX-MIX)<=64所以最后的时间复杂度为O(M+N)最后，放出源码[cpp] view plaincopy#include <iostream>using namespace std;struct Line{int left, right, count;Line *leftChild, *rightChild;Line(int l, int r): left(l), right(r) {}};//建立一棵空线段树void createTree(Line *root) {int left = root->left;int right = root->right;if (left < right) {int mid = (left + right) / 2;Line *lc = new Line(left, mid);Line *rc = new Line(mid + 1, right);root->leftChild = lc;root->rightChild = rc;createTree(lc);createTree(rc);}}//将线段[l, r]分割void insertLine(Line *root, int l, int r) {cout << l << " " << r << endl;cout << root->left << " " << root->right << endl << endl;if (l == root->left && r == root->right) {root->count += 1;} else if (l <= r) {int rmid = (root->left + root->right) / 2;if (r <= rmid) {insertLine(root->leftChild, l, r);} else if (l >= rmid + 1) {insertLine(root->rightChild, l, r);} else {int mid = (l + r) / 2;insertLine(root->leftChild, l, mid);insertLine(root->rightChild, mid + 1, r);}}}//树的中序遍历（测试用）void inOrder(Line* root) {if (root != NULL) {inOrder(root->leftChild);printf("[%d, %d], %d\n", root->left, root->right, root->count);inOrder(root->rightChild);}}//获取值n在线段上出现的次数int getCount(Line* root, int n) {int c = 0;if (root->left <= n&&n <= root->right)c += root->count;if (root->left == root->right)return c;int mid = (root->left + root->right) / 2;if (n <= mid)c += getCount(root->leftChild, n);elsec += getCount(root->rightChild, n);return c;}int main() {int l[3] = {2, 4, 0};int r[3] = {5, 6, 7};int MIN = l[0];int MAX = r[0];for (int i = 1; i < 3; ++i) {if (MIN > l[i]) MIN = l[i];if (MAX < r[i]) MAX = r[i];}Line *root = new Line(MIN, MAX);createTree(root);for (int i = 0; i < 3; ++i) {insertLine(root, l[i], r[i]);}inOrder(root);int N;while (cin >> N) {cout << getCount(root, N) << endl; }return 0;}。

线段树【完整版】单点更新:最最基础的线段树,只更新叶子节点,然后把信息用PushUP(int r)这个函数更新上来Hdu1754 I hate it线段树功能:update:单点替换 query:区间最值#include<iostream>#include<algorithm>using namespace std;int MAXN[4000001],d[4000001];void PushUp(int rt){MAXN[rt]=max(MAXN[rt<<1],MAXN[rt<<1|1]);}void build(int l,int r,int rt){if(l==r){cin>> MAXN[rt];return;}int m=(l+r)>>1;build(l,m,rt<<1);build(m+1,r,(rt<<1)+1);PushUp(rt);}void update(int p,int sc,int l,int r,int rt){if(l==r){MAXN[rt]=sc;return;}int m=(l+r)>>1;if(p<=m)update(p,sc,l,m,rt<<1);else update(p,sc,m+1,r,(rt<<1)+1);PushUp(rt);}int getmax(int L,int R,int l,int r,int rt){if(L<=l&&r<=R){return MAXN[rt];}int m=(l+r)>>1;int ret=0;if(L<=m)ret=max(ret,getmax(L,R,l,m,rt<<1));if(R>m)ret=max(ret,getmax(L,R,m+1,r,(rt<<1)+1));return ret;}int main(){int n,m,a,b;char ch;while(cin>>n>>m){build(1,n,1);for(int i=0;i<m;i++){cin>>ch>>a>>b;if(ch=='U')update(a,b,1,n,1);else cout<<getmax(a,b,1,n,1)<<endl;}}}hdu1166敌兵布阵线段树功能:update:单点增减 query:区间求和#include<iostream>#include<string>using namespace std;const int maxn=55555;int sum[maxn<<2];void PushUp(int rt){sum[rt]=sum[rt<<1]+sum[(rt<<1)+1];}void build(int l,int r,int rt){if(l==r){cin>>sum[rt];return;}int m=(l+r)>>1;build(l,m,rt<<1);build(m+1,r,(rt<<1)+1);PushUp(rt);}void update(int p,int add,int l,int r,int rt) {if(l==r){sum[rt]+=add;return;}int m=(l+r)>>1;if(p<=m)update(p,add,l,m,rt<<1);else update(p,add,m+1,r,(rt<<1)+1);PushUp(rt);}int getsum(int L,int R,int l,int r,int rt){if(L<=l&&r<=R){return sum[rt];}int m=(r+l)>>1;int ret=0;if(L<=m)ret+=getsum(L,R,l,m,rt<<1);if(R>m)ret+=getsum(L,R,m+1,r,(rt<<1)+1);return ret;}int main(){int cas,n,a,b,k=0;string s;cin>>cas;while(cas--){k++;cout<<"Case "<<k<<":"<<endl;cin>>n;build(1,n,1);while(cin>>s){if(s=="End")break;if(s=="Query"){cin>>a>>b;cout<<getsum(a,b,1,n,1)<<endl;}else if(s=="Add"){cin>>a>>b;update(a,b,1,n,1);}else{cin>>a>>b;update(a,-b,1,n,1);}}}}hdu1394 Minimum Inversion Number题意:求Inversion后的最小逆序数思路:用O(nlogn)复杂度求出最初逆序数后,就可以用O(1)的复杂度分别递推出其他解线段树功能:update:单点增减 query:区间求和#include<iostream>#include<algorithm>using namespace std;int sum[10001],x[5001];void PushUp(int rt){sum[rt]=sum[rt<<1]+sum[(rt<<1)+1];}void build(int l,int r,int rt){sum[rt]=0;if(l==r)return;int m=(l+r)>>1;build(l,m,rt<<1);build(m+1,r,(rt<<1)+1);}void update(int p,int l,int r,int rt){if(l==r){sum[rt]++;return;}int m=(l+r)>>1;if(p<=m)update(p,l,m,rt<<1);else update(p,m+1,r,(rt<<1)+1);PushUp(rt);}int GetReverse(int L,int R,int l,int r,int rt){if(L<=l&&r<=R)return sum[rt];int m=(l+r)>>1;int ret=0;if(L<=m)ret+=GetReverse(L,R,l,m,rt<<1);if(R>m)ret+=GetReverse(L,R,m+1,r,(rt<<1)+1);return ret;}int main(){int n;while(cin>>n){build(0,n-1,1);int sum=0;for(int i=0;i<n;i++){cin>>x[i];sum+=GetReverse(x[i],n-1,0,n-1,1);//求x[i]到n-1之间已存在几个数字，即求x[i]的逆序数update(x[i],0,n-1,1);//包含[x[i],x[i]]的区间+1}int ret=sum;for(int i=0;i<n;i++){//把第一个位子上的数(x[i])移到最后，则被移的数的逆序是n-1-x[i],而未被移的数字有x[i]个比x[i]小sum+=n-1-x[i]-x[i];ret=min(sum,ret);}cout<<ret<<endl;}}hdu2795Billboard题意:h*w的木板,放进一些1*L的物品,求每次放空间能容纳且最上边的位子思路:每次找到最大值的位子,然后减去L线段树功能:query:区间求最大值的位子(直接把update的操作在query里做了)#include<iostream>#include<algorithm>using namespace std;int MAX[222222<<2];int w;void PushUp(int rt){MAX[rt]=max(MAX[rt<<1],MAX[(rt<<1)|1]);}void build(int l,int r,int rt){MAX[rt]=w;//c初始化每行都有W的空间if(l==r)return;int m=(l+r)>>1;build(l,m,rt<<1);build(m+1,r,(rt<<1|1));}int query(int x,int l,int r,int rt){if(l==r){MAX[rt]-=x;return l;}int m=(l+r)>>1;int ret=(MAX[rt<<1] >= x? query(x ,l,m,rt<<1):query(x ,m+1,r,(rt<<1)|1)) ;//查找左边能放得下，优先左边PushUp(rt);return ret;}int main(){int h,n,x;while(scanf("%d%d%d",&h,&w,&n)==3){if(h>n)h=n;//题目中h>1,n<200000,h可能会大于所开的MAX[];build(1,h,1);for(int i=0;i<n;i++){scanf("%d",&x);if(x>MAX[1])printf("%d\n",-1);else printf("%d\n",query(x,1,h,1));}}}成段更新(通常这对初学者来说是一道坎),需要用到延迟标记(或者说懒惰标记),简单来说就是每次更新的时候不要更新到底,用延迟标记使得更新延迟到下次需要更新or询问到的时候hdu1698Just a Hook题意:O(-1)思路:O(-1)线段树功能:update:成段替换 (由于只query一次总区间,所以可以直接输出1结点的信息)#include <cstdio>#include <algorithm>using namespace std;const int maxn = 111111;int col[maxn<<2];int sum[maxn<<2];void PushUp(int rt){sum[rt]=sum[rt<<1]+sum[(rt<<1)|1];}void PushDown(int rt,int m){if(col[rt]){col[(rt<<1)|1]=col[rt<<1]=col[rt];sum[rt<<1]=col[rt]*(m-(m>>1));sum[(rt<<1)|1]=col[rt]*(m>>1);col[rt]=0;}}void build(int l,int r,int rt){col[rt]=0;sum[rt]=1;if(l==r)return;int m=(l+r)>>1;build(l,m,rt<<1);build(m+1,r,(rt<<1)|1);PushUp(rt);}void update(int L,int R,int c,int l,int r,int rt){if(L<=l&&r<=R){col[rt]=c;sum[rt]=(r-l+1)*c;return;}PushDown(rt,r-l+1);int m=(l+r)>>1;if(L<=m)update(L,R,c,l,m,rt<<1);if(R>m)update(L,R,c,m+1,r,(rt<<1)|1);PushUp(rt);}int main(){int cas,n,m,a,b,c,k=0;scanf("%d",&cas);while(cas--){k++;scanf("%d",&n);build(1,n,1);scanf("%d",&m);while(m--){scanf("%d%d%d",&a,&b,&c);update(a,b,c,1,n,1);}printf("Case %d: The total value of the hook is %d.\n",k,sum[1]); }}3468A Simple Problem with Integers线段树功能:update:成段增减 query:区间求和#include<iostream>#include<algorithm>using namespace std;const int maxn = 111111;long long int add[maxn<<2];long long int sum[maxn<<2];void PushUp(int rt){sum[rt]=sum[rt<<1]+sum[(rt<<1)|1];}void PushDown(int rt,int m){if(add[rt]){add[rt<<1]+=add[rt];add[(rt<<1)|1]+=add[rt];sum[rt<<1]+=add[rt]*(m-(m>>1));sum[(rt<<1)|1]+=add[rt]*(m>>1);add[rt]=0;}}void build(int l,int r,int rt){add[rt]=0;if(l==r){cin>>sum[rt];return;}int m=(l+r)>>1;build(l,m,rt<<1);build(m+1,r,(rt<<1)|1);PushUp(rt);}void update(int L,int R,int c,int l,int r,int rt){if(L<=l&&r<=R){add[rt]+=c;sum[rt]+=(long long int)(r-l+1)*c;return;}PushDown(rt,r-l+1);int m=(l+r)>>1;if(L<=m)update(L,R,c,l,m,rt<<1);if(R>m)update(L,R,c,m+1,r,(rt<<1)|1);PushUp(rt);}long long int query(int L,int R,int l,int r,int rt){if(L<=l&&r<=R)return sum[rt];PushDown(rt,r-l+1);int m=(l+r)>>1;long long int ret=0;if(L<=m)ret+=query(L,R,l,m,rt<<1);if(m<R)ret+=query(L,R,m+1,r,(rt<<1)|1);return ret;}int main(){int n,m,a,b,c;char ch;while(cin>>n>>m){build(1,n,1);for(int i=0;i<m;i++){cin>>ch;if(ch=='C'){cin>>a>>b>>c;update(a,b,c,1,n,1);}else {cin>>a>>b;cout<<query(a,b,1,n,1)<<endl;}}}}poj2528Mayor's posters题意:在墙上贴海报,海报可以互相覆盖,问最后可以看见几张海报思路:这题数据范围很大,直接搞超时+超内存,需要离散化:离散化简单的来说就是只取我们需要的值来用,比如说区间[1000,2000],[1990,2012] 我们用不到[-∞,999][1001,1989][1991,1999][2001,2011][2013,+∞]这些值,所以我只需要1000,1990,2000,2012就够了,将其分别映射到0,1,2,3,在于复杂度就大大的降下来了所以离散化要保存所有需要用到的值,排序后,分别映射到1~n,这样复杂度就会小很多很多而这题的难点在于每个数字其实表示的是一个单位长度(并且一个点),这样普通的离散化会造成许多错误(包括我以前的代码,poj这题数据奇弱)给出下面两个简单的例子应该能体现普通离散化的缺陷:1-10 1-4 5-101-10 1-4 6-10为了解决这种缺陷,我们可以在排序后的数组上加些处理,比如说[1,2,6,10]如果相邻数字间距大于1的话,在其中加上任意一个数字,比如加成[1,2,3,6,7,10],然后再做线段树就好了.线段树功能:update:成段替换 query:简单hash#include<iostream>#include<algorithm>#include<cstring>using namespace std;const int maxn=11111;int col[maxn<<4],le[maxn],ri[maxn],X[maxn*3],hash[maxn];int ans;void PushDown(int rt){if(col[rt]!=-1){col[rt<<1]=col[(rt<<1)|1]=col[rt];col[rt]=-1;}}void update(int L,int R,int c,int l,int r,int rt){if(L<=l&&r<=R){col[rt]=c;return;}PushDown(rt);int m=(l+r)>>1;if(L<=m)update(L,R,c,l,m,rt<<1);if(R>m)update(L,R,c,m+1,r,(rt<<1)|1);}void query(int l,int r,int rt){if(col[rt]!=-1){if(!hash[col[rt]]){ans++;hash[col[rt]]=1;}return;}if(l==r)return;int m=(l+r)>>1;query(l,m,rt<<1);query(m+1,r,(rt<<1)|1);}int Bin(int key,int n){int l=0,r=n-1;while(l<=r){int m=(l+r)>>1;if(X[m]==key)return m;if(X[m]>key) r=m-1;else l=m+1;}return -1;}int main(){int cas,n;cin>>cas;while(cas--){cin>>n;int nn=0;for(int i=0;i<n;i++){cin>>le[i]>>ri[i];X[nn++]=le[i],X[nn++]=ri[i];}sort(X,X+nn);int m=1;for(int i=1;i<nn;i++)if(X[i]!=X[i-1])X[m++]=X[i];for(int i=m-1;i>0;i--)if(X[i]!=X[i-1]+1)X[m++]=X[i-1]+1;sort(X,X+m);memset(col,-1,sizeof(col));for(int i=0;i<n;i++){int l=Bin(le[i],m);int r=Bin(ri[i],m);update(l,r,i,0,m,1);}ans=0;memset(hash,0,sizeof(hash));query(0,m,1);cout<<ans<<endl;}}区间合并这类题目会询问区间中满足条件的连续最长区间,所以PushUp的时候需要对左右儿子的区间进行合并poj3667Hotel题意:1 a:询问是不是有连续长度为a的空房间,有的话住进最左边2 a b:将[a,a+b-1]的房间清空思路:记录区间中最长的空房间线段树操作:update:区间替换 query:询问满足条件的最左断点#include<iostream>#include<algorithm>using namespace std;const int maxn=50000;int cover[maxn<<2];int lsum[maxn<<2],rsum[maxn<<2],msum[maxn<<2];void PushUp(int rt,int m){lsum[rt]=lsum[rt<<1],rsum[rt]=rsum[(rt<<1)|1];if(lsum[rt<<1]==m-(m>>1))lsum[rt]+=lsum[(rt<<1)|1];if(rsum[(rt<<1)|1]==m>>1)rsum[rt]+=rsum[rt<<1];msum[rt]=max(max(msum[rt<<1],msum[(rt<<1)|1]),rsum[rt<<1]+lsum[(rt<<1)|1]); }void PushDown(int rt,int m){if(cover[rt]!=-1){cover[rt<<1]=cover[(rt<<1)|1]=cover[rt];lsum[rt<<1]=rsum[rt<<1]=msum[rt<<1]=(cover[rt]? 0:m-(m>>1));lsum[(rt<<1)|1]=rsum[(rt<<1)|1]=msum[(rt<<1)|1]=(cover[rt]? 0:m>>1);cover[rt]=-1;}}void build(int l,int r,int rt){cover[rt]=-1;lsum[rt]=rsum[rt]=msum[rt]=r-l+1;if(l==r)return;int m=(l+r)>>1;build(l,m,rt<<1);build(m+1,r,(rt<<1)|1);}void update(int L,int R,int c,int l,int r,int rt){if(L<=l&&r<=R){cover[rt]=c;lsum[rt]=rsum[rt]=msum[rt]=(c? 0:r-l+1);return;}PushDown(rt,r-l+1);int m=(l+r)>>1;if(L<=m)update(L,R,c,l,m,rt<<1);if(R>m)update(L,R,c,m+1,r,(rt<<1)|1);PushUp(rt,r-l+1);}int query(int w,int l,int r,int rt){if(l==r)return l;PushDown(rt,r-l+1);int m=(l+r)>>1;if(msum[rt<<1]>=w)return query(w,l,m,rt<<1);else if(rsum[rt<<1]+lsum[(rt<<1)|1]>=w)return m-rsum[rt<<1]+1;else query(w,m+1,r,(rt<<1)|1);}int main(){int n,m,a,b,c;while(cin>>n>>m){build(1,n,1);while(m--){cin>>a;if(a==1){cin>>b;if(msum[1]<b){cout<<0<<endl;continue;}int ans=query(b,1,n,1);cout<<ans<<endl;update(ans,ans+b-1,1,1,n,1);}else{cin>>b>>c;update(b,b+c-1,0,1,n,1);}}}}hdu3911Black And White题意：给出01串 1代表黑色 0代表白色0 a b:询问[a,b]中1的连续最大长度1 a,b:把[a,b]区间的0->1 1->0思路：lsum1[],rsum1[],msum1[]分别表示区间做起连续1的最大长度，右起连续1的最大长度，区间1的最大连续长度lsum0[],rsum0[],msum0[]分别表示区间做起连续0的最大长度，右起连续0的最大长度，区间连续0的最大连续长度0 a b:交换 0和1的lsum[] rsum[] msum[]; ROX[]表示需要向儿子更新两次更新=不变线段树功能：update区间替换，query询问区间1的最大连续长度#include<iostream>#include<stdio.h>#include<algorithm>using namespace std;const int maxn=100001;int ROX[maxn<<2];int lsum1[maxn<<2],rsum1[maxn<<2],msum1[maxn<<2];int lsum0[maxn<<2],rsum0[maxn<<2],msum0[maxn<<2];void PushUp(int rt,int m){lsum1[rt]=lsum1[rt<<1],rsum1[rt]=rsum1[(rt<<1)|1];if(lsum1[rt<<1]==m-(m>>1))lsum1[rt]+=lsum1[(rt<<1)|1];if(rsum1[(rt<<1)|1]==m>>1)rsum1[rt]+=rsum1[rt<<1];msum1[rt]=max(max(msum1[rt<<1],msum1[(rt<<1)|1]),rsum1[rt<<1]+lsum1[(rt<<1)|1]);lsum0[rt]=lsum0[rt<<1],rsum0[rt]=rsum0[(rt<<1)|1];if(lsum0[rt<<1]==m-(m>>1))lsum0[rt]+=lsum0[(rt<<1)|1];if(rsum0[(rt<<1)|1]==m>>1)rsum0[rt]+=rsum0[rt<<1];msum0[rt]=max(max(msum0[rt<<1],msum0[(rt<<1)|1]),rsum0[rt<<1]+lsum0[(rt<<1)|1]);}void PushDown(int rt,int m){if(ROX[rt]){ROX[rt<<1]^=1,ROX[(rt<<1)|1]^=1;swap(lsum0[rt<<1],lsum1[rt<<1]),swap(rsum1[rt<<1],rsum0[rt<<1]),swap(msum1[rt<<1],msum0[rt<<1]); swap(lsum0[(rt<<1)|1],lsum1[(rt<<1)|1]), swap(rsum1[(rt<<1)|1],rsum0[(rt<<1)|1]),swap(msum1[(rt<<1)|1],msum0[(rt<<1)|1]);ROX[rt]=0;}}void build(int l,int r,int rt){ROX[rt]=0;if(l==r){int c;scanf("%d",&c);lsum1[rt]=rsum1[rt]=msum1[rt]=c;lsum0[rt]=rsum0[rt]=msum0[rt]=c^1;return;}int m=(l+r)>>1;build(l,m,rt<<1);build(m+1,r,(rt<<1)|1);PushUp(rt,r-l+1);}void update(int L,int R,int l,int r,int rt){if(L<=l&&r<=R){ROX[rt]^=1;swap(lsum0[rt],lsum1[rt]),swap(rsum1[rt],rsum0[rt]),swap(msum1[rt],msum0[rt]);return;}PushDown(rt,r-l+1);int m=(l+r)>>1;if(L<=m)update(L,R,l,m,rt<<1);if(R>m)update(L,R,m+1,r,(rt<<1)|1);PushUp(rt,r-l+1);}int query(int L,int R,int l,int r,int rt){if(L<=l&&r<=R)return msum1[rt];int tmp;PushDown(rt,r-l+1);int m=(l+r)>>1;if(m>=R) tmp=query(L,R,l,m,rt<<1);else if(m<L)tmp=query(L,R,m+1,r,(rt<<1)|1);elsetmp=max(query(L,R,l,m,rt<<1),query(L,R,m+1,r,(rt<<1)|1));int tmp1=min(m-L+1,rsum1[rt<<1]);int tmp2=min(R-m,lsum1[(rt<<1)|1]);tmp=max(tmp,tmp1+tmp2);}return tmp;}int main(){int n,m,a,b,c;while(scanf("%d",&n)==1){build(1,n,1);scanf("%d",&m);while(m--){scanf("%d%d%d",&a,&b,&c);if(a==1)update(b,c,1,n,1);else cout<<query(b,c,1,n,1)<<endl;}}}扫描线这类题目需要将一些操作排序,然后从左到右用一根扫描线(当然是在我们脑子里)扫过去最典型的就是矩形面积并,周长并等题hdu1542Atlantis题意:矩形面积并思路:浮点数先要离散化;然后把矩形分成两条边,上边和下边,对横轴建树,然后从下到上扫描上去,用cnt表示该区间下边比上边多几个线段树操作:update:区间增减 query:直接取根节点的值#include<iostream>#include<algorithm>#include<cstring>#include<iomanip>using namespace std;const int maxn=201;int cnt[maxn<<2];double X[maxn<<1],sum[maxn<<2];struct Seg{double l,r,h;int c;Seg(){};Seg(double _l,double _r,double _h,int _c):l(_l),r(_r),h(_h),c(_c){};bool operator <(const Seg& cmp){return h<cmp.h;}}s[maxn<<2];void PushUp(int rt,int l,int r){if(cnt[rt])sum[rt]=X[r+1]-X[l];else if(l==r)sum[rt]=0;else sum[rt]=sum[rt<<1]+sum[(rt<<1)|1];void update(int L,int R,int c,int l,int r,int rt){if(L<=l&&r<=R){cnt[rt]+=c;PushUp(rt,l,r);return;}int m=(l+r)>>1;if(L<=m)update(L,R,c,l,m,rt<<1);if(R>m)update(L,R,c,m+1,r,(rt<<1)|1);PushUp(rt,l,r);}int Bin(double key,int n){int l=0,r=n-1;while(l<=r){int m=(l+r)>>1;if(X[m]==key)return m;if(key<X[m])r=m-1;else l=m+1;}return -1;}int main(){cout.precision(2);int n,cas=0;double a,b,c,d;while(cin>>n&&n){cas++;int m=0;for(int i=0;i<n;i++){cin>>a>>b>>c>>d;s[m]=Seg(a,c,b,1);X[m++]=a;s[m]=Seg(a,c,d,-1);X[m++]=c;}sort(X,X+m);sort(s,s+m);int k=1;double ans=0;for(int i=1;i<m;i++)if(X[i]!=X[i-1])X[k++]=X[i];memset(cnt,0,sizeof(cnt));memset(sum,0,sizeof(sum));for(int i=0;i<m;i++){int l=Bin(s[i].l,k);int r=Bin(s[i].r,k)-1;if(l <= r) update(l,r,s[i].c,0,k-1,1);ans+=sum[1]*(s[i+1].h-s[i].h);}cout<<"Test case #"<<cas<<endl;cout<<"Total explored area: "<<fixed<<ans<<endl;cout<<endl;}}hdu1828Picture题意:矩形周长并思路:与面积不同的地方是还要记录竖的边有几个(numseg记录),并且当边界重合的时候需要合并(用lbd和rbd表示边界来辅助)线段树操作:update:区间增减 query:直接取根节点的值#include<iostream>#include<algorithm>#include<cmath>using namespace std;const int maxn=20001;int len[maxn<<2],lbd[maxn<<2],rbd[maxn<<2],cnt[maxn<<2],numSeg[maxn<<2];struct Seg{int l,r,h,c;Seg(){};Seg(int _l,int _r,int _h,int _c):l(_l),r(_r),h(_h),c(_c){};bool operator<(Seg&a){return h<a.h;}}s[maxn];void PushUp(int rt,int l,int r){if(cnt[rt]){lbd[rt]=rbd[rt]=1;len[rt]=r-l+1;numSeg[rt]=2;}else if(l==r){lbd[rt]=rbd[rt]=len[rt]=numSeg[rt]=0;}else{lbd[rt]=lbd[rt<<1],rbd[rt]=rbd[(rt<<1)|1];len[rt]=len[rt<<1]+len[(rt<<1)|1];numSeg[rt]=numSeg[rt<<1]+numSeg[(rt<<1)|1];if(rbd[rt<<1]&&lbd[(rt<<1)|1])numSeg[rt]-=2;}}void update(int L,int R,int c,int l,int r,int rt){if(L<=l&&r<=R){cnt[rt]+=c;PushUp(rt,l,r);return;}int m=(l+r)>>1;if(L<=m)update(L,R,c,l,m,rt<<1);if(R>m)update(L,R,c,m+1,r,(rt<<1)|1);PushUp(rt,l,r);}int main(){int n,a,b,c,d;while(cin>>n){int m=0,lmin=10000,rmax=-10000;for(int i=0;i<n;i++)cin>>a>>b>>c>>d;lmin=min(lmin,a);rmax=max(rmax,c);s[m++]=Seg(a,c,b,1);s[m++]=Seg(a,c,d,-1);}sort(s,s+m);int ret=0,last=0;for(int i=0;i<m;i++){if(s[i].l < s[i].r)update(s[i].l,s[i].r-1,s[i].c,lmin,rmax-1,1);ret+=numSeg[1]*(s[i+1].h-s[i].h);ret+=abs(len[1]-last);last=len[1];}cout<<ret<<endl;}}。

线段树（数组实现）最近看了很多学长发的资料，吸取了别⼈的优点，把query函数更改的更加合理了。

—————————————————————我是分割线————————————————————————————————————————————　　线段树是⼀棵完美⼆叉树，树上的每个节点都维护⼀个区间。

根维护的是整个区间，每个节点维护的是⽗亲的区间⼆等分后的其中⼀个⼦区间。

当有n个元素时，对区间的操作可以在O（logn）的时间内完成。

所以，线段树是擅长处理区间的！ 从⽹上找了⼀个图：RMQ(range minimum query)问题： 在给定数列a0,a1...a n，给定s和t，线段树可以求a s...a t的最值，以求最⼩值为例，如下图： 每个节点维护对应区间的最⼩值，例如根节点维护的是下标1到8的最⼩值，左⼦树维护的是1到4，右⼦书维护的是5到6，以此类推。

建树时，⽗节点取左右⼦节点的较⼩者。

我⽐较喜欢⽤数组建树，因为⾮常简单清晰，下⾯是初始化线段树的代码：1#define max 9999999992int k,n,tree[10005];//n这⾥是数列⾥数字的个数3void init(){4 k=1;//k这⾥是树最后⼀层的叶⼦个数5while(k<n)//除第⼀层外，树的每⼀层都有2的n次⽅个节点，所以这⾥求的是k⼤于n的最⼩节点数6 k<<=1;//输⼊的数字个数n可能⼩于最下⾯⼀层的叶⼦数7for(int i=1;i<=2*k-1;i++)//2*k-1是整个树节点的个数，全部设置为max，反正⽗节点取的是较⼩者8 tree[i]=max;9 } n⼩于k时，树最后⼀层的其他值已经是max，所以不影响⽗节点，下⾯是线段树每插⼊⼀个值的更新：1void update(int pos,int val){//pos是树的下标，val是数的值2 pos+=k-1;//这⾥数组下标是从1到n，树的下标也是从1到n，这就是叶⼦节点与数组下标的对应关系，⼤家可以画⼀画3 tree[pos]=val;4while(k>1){5 pos/=2;//⽗节点6 tree[pos]=tree[pos*2]<tree[pos*2+1]?tree[pos*2]:tree[pos*2+1];7 }8 } 下⾯⽐较关键的是给定下标区间查找，我会在注释⾥说明：1//调⽤时query(输⼊a,输⼊b,1,1,k)2int query(int a,int b,int pos,int l,int r){//a和b是想要查找的下标区间，l和r是当前节点维护的下标区间，pos是当前节点下标3if(a<=l&&b>=r)//查找终结的条件就是想查找的区间⼤于节点维护的区间4return tree[pos];5int mid = (l+r)/2;6if(a<=m)7int a = query(a,b,pos*2,l,m);8if(b>m)9int b = query(a,b,pos*2+1,m+1,r);10return a<b?a:b;11 } OK，到这⾥，基本的算法就实现了，注意⼀下树的⼤⼩⼀定要合适。