😊 | Powered By HeartFireY | Weighted Segment Tree
 
一、权值线段树 简介
 
1.线段树
 
线段树是一种用于维护区间信息的高效数据结构，可以在 $O(\log N)$ 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。
 
线段树维护的信息必须满足可加性，即能以可以接受的速度合并信息和修改信息，包括在使用Lazy标记时，标记也要满足可加性
 
具体有关线段树的的讲解请参考博客：线段树 详解与模板
 
2.权值线段树
 
权值线段树是一种建立在基本线段树之上的数据结构。因此它的基本原理仍是基于对区间的维护操作。但与线段树相区分的点是：权值线段树维护的信息与基本线段树有所差异：
 
基本线段树中每个系欸但用来维护一段区间的最大值或总和等；
权值线段树每个结点维护的是一个区间的数出现的次数。
 
实际上，权值线段树可以看作是一个桶，桶的操作它都支持，并且能够以更快的方式去完成。
 
根据权值线段树的性质，我们可以知道其主要用途：
 
权值线段树一般用于维护一段区间的数出现的次数，从它的定义来看，它可以快速计算出一段区间的数的出现次数。
 
在实际应用中，我们使用权值线段树查询区间第$K$大的值。
 
二、权值线段树的基本原理与操作
 
1.权值线段树维护信息的原理
 
基础线段树和权值线段树的一个较大的区别点在于：(此处特指使用数组储存树结构)基础线段树根据初始的一个序列建立树结构，具有单独的建树操作；而权值线段树不需要进行建树操作，初始状态下默认建立一棵所有点权为$0$的空树，对于每个元素，在遍历的时候相应的结点做自增运算。换而言之：
 
权值线段是一棵已经建好的线段树，储存树结构的下标范围根据区间最大值最小值确定(一般开大空间即可)；
初始状态下所有的点权均为$0$；
执行插入元素的操作时，会导致插入值$v$对应的$A[v]++$，同时引发单点更新操作。
可以从上述描述中得到基本推论：向空的权值线段树中插入一个无序序列，则插入完成后在树上无法再得到原序列的遍历，但能通过遍历得到有序序列(无序序列变有序序列)
 
我们可以通过结构对比线段树与权值线段树的区别，以此理解原理。
 
我们给定序列
    
     
      
       
        {
       
       
        1
       
       
        ,
       
       
        2
       
       
        ,
       
       
        2
       
       
        ,
       
       
        3
       
       
        ,
       
       
        3
       
       
        ,
       
       
        3
       
       
        ,
       
       
        4
       
       
        ,
       
       
        4
       
       
        ,
       
       
        4
       
       
        ,
       
       
        4
       
       
        }
       
      
      
       \{1, 2, 2, 3, 3, 3, 4, 4, 4, 4 \}
      
     
    {1,2,2,3,3,3,4,4,4,4}，以该序列为例建立两种线段树。
 
首先，序列长度为$10$，建立基础区间和查询线段树，结构图如下：
 
 
对应具体的细节不再阐述。我们继续建立权值线段树：首先给出一棵空树：
 
(注：为演示方便，A数组下标做+1操作，树上的范围也对应变化，这里懒得改了~)
 
 
然后按照序列顺序插入元素：
 
 
解释：
 
$A[1]=1$：原序列中存在值为$1$的元素$1$个
 $A[2]=1$：原序列中存在值为$2$的元素$2$个
 $A[3]=1$：原序列中存在值为$3$的元素$3$个
 $A[4]=1$：原序列中存在值为$4$的元素$4$个
 
$D[k]$：一定区间内所含元素的个数
 
我们继续探究查找第$K$大元素的方法：
 
由于权值线段树每个节点记录了某段区间内包含的元素个数，且元素在叶子节点构成的序列中是有序的：
 
对于整列数中第$K$大/小的值，我们从根节点开始判断（这里按第$K$大为例），如果$K$比右儿子大，就说明第$K$大的数在左儿子所表示的值域中。然后，$K$要减去右儿子。（这是因为继续递归下去的时候，正确答案，整个区间的第$K$大已经不再是左儿子表示区间的第$K$大了)。如此递归到叶子节点时即为答案。
整棵线段树的根节点就表示整个值域有几个数。
 
我们很容易看出：在权值线段树中，采用元素到下标数组映射的方式进行插入。这样会导致一个问题：在数据离散程度较大的情况下，空间的利用效率比较低。因此我们对于线段树所开空间不足时，常采用离散化的方式进行解决。
 
📕 | 此处的前导知识：离散化(具体的参见离散化的讲解)
 
2.权值线段树的基本操作与实现
 
①.查询第$K$大/小元素
 
假设$K=5$，那么查询过程是怎样的？
 
首先我们从根节点出发，由于要查询第$K$大，是相对于终点而言的，因此从右子结点开始判断：
 
 
当前节点右子树包含$4$个元素，所以应该向左子树遍历，注意：此时应该减去右子树的$4$个元素！
 
 
寻找第$K$小的操作与上方类似，区别在于相对于起点OR终点而言(遍历时对左右子树的判断顺序)。
 
再次回顾整个步骤：对于整列数中第$K$大/小的值，我们从根节点开始判断（这里按第$K$大为例），如果$K$比右儿子大，就说明第$K$大的数在左子树中。然后，$K$要减去右子节点的值。（这是因为继续递归下去的时候，正确答案，整个区间的第$K$大已经不再是左子树表示区间的第$K$大了)。如此递归到叶子节点时即为答案
 
根据以上分析步骤，我们可以写出查询第$K$大和第$K$小的函数：
 
int query_kth(int pos, int l, int r, int k){
    if(l == r) return l;
    int mid = (l + r) >> 1, right = tree[pos << 1 | 1];
    if(k <= right) return query(pos << 1 | 1, mid + 1, r, k);
    else return query(pos << 1, l, mid, k - right);
}
 
int query_kth(int pos, int l, int r, int k){
    if(l == r) return l;
    int mid = (l + r) >> 1, left = tree[pos << 1];
    if(k <= left) return query(pos << 1, l, mid, k - left);
    else return query(pos << 1 | 1, mid + 1, r, k);
}
 
②.单点更新操作
 
类似基础线段树，递归到叶子节点$+1$然后回溯
 
void add(int l, int r, int v, int x){
    if (l == r) tree[v]++;
    else{
        int mid = (l + r) >> 1;
        if (x <= mid) add(l, mid, v << 1, x);
        else add(mid + 1, r, v << 1 | 1, x);
        tree[v] = tree[v << 1] + tree[v << 1 | 1];
    }
}
 
③.查询某个数出现的个数
 
树上二分查找的思想，代码如下：
 
int find(int l, int r, int v, int x){
    if (l == r) return tree[v];
    else{
        int mid = (l + r) >> 1;
        if (x <= mid) return find(l, mid, v << 1, x);
        else return find(mid + 1, r, v << 1 | 1, x);
    }
}
 
④.查询一段区间的数出现的次数
 
int find(int l, int r, int v, int x, int y){
    if (l == x && r == y) return tree[v];
    else{
        int mid = (l + r) >> 1;
        if (y <= mid) return find(l, mid, v << 1, x, y);
        else if (x > mid) return find(mid + 1, r, v << 1 | 1, x, y);
        else return find(l, mid, v << 1, x, mid) + find(mid + 1, r, v << 1 | 1, mid + 1, y);
    }
}
 
3.区间离散化
 
如前所述，在将元素个数映射到叶子节点的过程中，离散程度较大时会导致极低的空间利用效率。对本种数据结构，我们关心的仅仅是元素之间的大小关系，因此可以采用离散化的方法对空间进行优化。
 
离散化的知识在此不展开赘述，直接采用C++STL算法
 
int get_discretization(){
    for (int i = 1; i <= n; ++i) a[i] = read(), b[i] = a[i]; //读入数据
    sort(b + 1, b + n + 1);
    int len = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= n; ++i){
        int pos = lower_bound(b + 1, b + len + 1, a[i]) - b;
        a[i] = pos;
    } //离散化
}

 
目录
 
第一部 概念引入
第二部 简单（无pushdown）的线段树
1、单点修改，区间查询
2、区间修改，单点查询
  
第三部 进阶线段树
第四部 乘法（根号）线段树
1、乘法线段树
2、根号线段树
模板题与代码：
单点修改，区间查询：洛谷树状数组模板1
区间修改，单点查询：洛谷树状数组模板2
区间加法，洛谷线段树模板1
区间乘法：洛谷线段树模板2
区间根号，bzoj3211
 

 
线段树是什么？？线段树怎么写？？
 
如果你在考提高组前一天还在问这个问题，那么你会与一等奖失之交臂；如果你还在冲击普及组一等奖，那么这篇博客会浪费你人生中宝贵的5~20分钟。
 
上面两句话显而易见，线段树这个数据结构是一个从萌新到正式OI选手的过渡，是一个非常重要的算法，也是一个对于萌新来说较难的算法。不得不说，我学习了这个算法5遍左右才有勇气写的这篇博客。
 
但是，对于OI正式选手来说，线段树不是算法，应该是一种工具。她能把一些对于区间（或者线段）的修改、维护，从O(N)的时间复杂度变成O（logN）。
 
第一部：线段树概念引入
 
第二部：简单(无pushdown）的线段树
 
第三部：区间+/-修改与查询
 
第四部：区间乘除修改与查询
 
第一部 概念引入
 
线段树是一种二叉树，也就是对于一个线段，我们会用一个二叉树来表示。比如说一个长度为4的线段，我们可以表示成这样：
 
 
这是什么意思呢？ 如果你要表示线段的和，那么最上面的根节点的权值表示的是这个线段1-4的和。根的两个儿子分别表示这个线段中1-2的和，与2-3的和。以此类推。
 
然后我们还可以的到一个性质：节点i的权值=她的左儿子权值+她的右儿子权值。因为1-4的和就是等于1-2的和2-3的和。
 
根据这个思路，我们就可以建树了，我们设一个结构体tree，tree[i].l和tree[i].r分别表示这个点代表的线段的左右下标，tree[i].sum表示这个节点表示的线段和。
 
我们知道，一颗二叉树，她的左儿子和右儿子编号分别是她*2和她*2+1
 
再根据刚才的性质，得到式子：$tree[i].sum=tree[i\ast 2].sum+tree[i\ast 2+1].sum;$就可以建一颗线段树了！代码如下：
 
inline void build(int i,int l,int r){//递归建树
    tree[i].l=l;tree[i].r=r;
    if(l==r){//如果这个节点是叶子节点
        tree[i].sum=input[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(i*2,l,mid);//分别构造左子树和右子树
    build(i*2+1,mid+1,r);
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;//刚才我们发现的性质return ;
}
 
嗯，这就是线段树的构建，你可能会问为什么要开好几倍的内存去储存一条线段。这是因为我们还没有让这个过大的数组干一些实事，那么什么是实事呢？让我们进入下一部（在你看懂这一部的情况下）
 
第二部 简单（无pushdown）的线段树
 
1、单点修改，区间查询
 
其实这一章开始才是真正的线段树，我们要用线段树干什么？答案是维护一个线段（或者区间），比如你想求出一个1100区间中，467这些元素的和，你会怎么做？朴素的做法是for(i=4;i<=67;i++) sum+=a[i]，这样固然好，但是算得太慢了。
 
我们想一种新的方法，先想一个比较好画图的数据，比如一个长度为4的区间，分别是1、2、3、4,我们想求出第1~3项的和。按照上一部说的，我们要建出一颗线段树，其中点权（也就是红色）表示和：
 
 
然后我们要求1-3的和，我们先从根节点开始查询，发现她的左儿子1-2这个区间和答案区间1~3有交集，那么我们跑到左儿子这个区间。
 
然后，我们发现这个区间1-2被完全包括在答案区间1~3这个区间里面，那就把她的值3返回。
 
我们回到了1-4区间，发现她的右儿子3-4区间和答案区间1~3有交集，那么我们走到3-4区间
 
到了3-4区间，我们发现她并没有完全包含在答案区间1-3里面，但发现她的左儿子3-3区间和1~3区间又交集，那么久走到3-3区间
 
到了3~3区间，发现其被答案区间完全包含，就返回她的值3一直到最开始
 
3-3区间的3+1-2区间的3=6，我们知道了1~3区间和为6.
 
有人可能会说你这样是不是疯了，我那脚都能算出1+2+3=6，为什么这么麻烦？！
 
因为这才几个数，如果一百万个数，这样时间会大大增快。
 
我们总结一下，线段树的查询方法：
 
 
如果这个区间被完全包括在目标区间里面，直接返回这个区间的值
 
 
如果这个区间的左儿子和目标区间有交集，那么搜索左儿子
 
 
如果这个区间的右儿子和目标区间有交集，那么搜索右儿子
 
 
写成代码，就会变成这样：
 
inline int search(int i,int l,int r){
    if(tree[i].l>=l && tree[i].r<=r)//如果这个区间被完全包括在目标区间里面，直接返回这个区间的值
        return tree[i].sum;
    if(tree[i].r<l || tree[i].l>r)  return 0;//如果这个区间和目标区间毫不相干，返回0
    int s=0;
    if(tree[i*2].r>=l)  s+=search(i*2,l,r);//如果这个区间的左儿子和目标区间又交集，那么搜索左儿子
    if(tree[i*2+1].l<=r)  s+=search(i*2+1,l,r);//如果这个区间的右儿子和目标区间又交集，那么搜索右儿子
    return s;
}
 
关于那几个if的条件一定要看清楚，最好背下来，以防考场上脑抽推错。
 
然后,我们怎么修改这个区间的单点，其实这个相对简单很多，你要把区间的第dis位加上k。
 
那么你从根节点开始，看这个dis是在左儿子还是在右儿子，在哪往哪跑，
 
然后返回的时候，还是按照tree[i].sum=tree[i*2].sum+tree[i*2+1].sum的原则，更新所有路过的点
 
如果不理解，我还是画个图吧，其中深蓝色是去的路径，浅蓝色是返回的路径，回来时候红色的+标记就是把这个点加上这个值。
 
 
把这个过程变成代码，就是这个样子：
 
inline void add(int i,int dis,int k){
    if(tree[i].l==tree[i].r){//如果是叶子节点，那么说明找到了
        tree[i].sum+=k;
        return ;
    }
    if(dis<=tree[i*2].r)  add(i*2,dis,k);//在哪往哪跑
    else  add(i*2+1,dis,k);
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;//返回更新
    return ;
}
 
2、区间修改，单点查询
 
区间修改和单点查询，我们的思路就变为：如果把这个区间加上k，相当于把这个区间涂上一个k的标记，然后单点查询的时候，就从上跑道下，把沿路的标记加起来就好。
 
这里面给区间贴标记的方式与上面的区间查找类似，原则还是那三条，只不过第一条：如果这个区间被完全包括在目标区间里面，直接返回这个区间的值变为了如果这个区间如果这个区间被完全包括在目标区间里面，讲这个区间标记k
 
具体做法很像，这里贴上代码：
 
inline void add(int i,int l,int r,int k){
    if(tree[i].l>=l && tree[i].r<=r){//如果这个区间被完全包括在目标区间里面，讲这个区间标记k
        tree[i].sum+=k;
        return ;
    }
    if(tree[i*2].r>=l)
        add(i*2,l,r,k);
    if(tree[i*2+1].l<=r)
        add(i*2+1,l,r,k);
}
 
然后就是单点查询了，这个更好理解了，就是dis在哪往哪跑，把路径上所有的标价加上就好了：
 
void search(int i,int dis){
    ans+=tree[i].sum;//一路加起来
    if(tree[i].l==tree[i].r)
        return ;
    if(dis<=tree[i*2].r)
        search(i*2,dis);
    if(dis>=tree[i*2+1].l)
        search(i*2+1,dis);
}
 
完整测试代码：
 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;

int n, m, s, t;
int ans;
int a[maxn];
struct segment_tree
{	
	struct node
	{
		int l, r;
		int num;
	}tr[maxn];
	
	void build(int p, int l, int r)
	{
		tr[p] = {l, r, 0};
		if(l == r) {
			tr[p].num = a[l];
			return ;
		}
		int mid = l + r >> 1;
		build(p << 1, l, mid);
		build(p << 1 | 1, mid + 1, r);
	}		
	
	void modify(int p, int l, int r, int k) 
	{
		if(tr[p].l >= l && tr[p].r <= r) {
			tr[p].num += k;
			return ;
		}
		int mid = tr[p].l + tr[p].r >> 1;
		if(l <= mid) modify(p << 1, l, r, k);
		if(r > mid) modify(p << 1 | 1, l, r, k);
	}
	
	void query(int p, int x)
	{
		ans += tr[p].num;
		if(tr[p].l == tr[p].r) return 	;
		int mid = tr[p].l + tr[p].r >> 1;
		if(x <= mid) query(p << 1, x);
		else query(p << 1 | 1, x); 
	}
}ST;

int main()
{
	n = 100;
	for (int i = 1; i <= n; ++ i) {
		a[i] = i;
	}
	ST.build(1, 1, n);
	m = 10;
	while(m -- ) {
		int l = 1, r = 100;
		ST.modify(1, l, r, 10000);
		ans = 0;
		ST.query(1, 50);
		//cout << ans << endl;
		ans = 0;
		ST.query(1, 100);
		cout << ans << endl;
	}
	return 0;
}
 
输入：
 
（无）
 
输出：
 
10100
20100
30100
40100
50100
60100
70100
80100
90100
100100

 
 
不知不觉，这第二章已经结束。这样的简单（原谅我用这个词）线段树，还可除了求和，还可以求区间最小最大值，还可以区间染色。
 
但是！这样的线段树展现不出来她的魅力，因为区间求和，树状数组比她少了一个很大的常数。二区间最值，ST表的那神乎其技 $O(1)$ 查询也能完爆她。这是为什么？因为线段树的魅力还没有展现出来，她最美丽的地方：pushdown还未展现于世，如果你已经对这一章充足的了解，并且能不看博客把洛谷上树状数组模板1、2都能写出来，那么请你进入下一部。
 
第三部 进阶线段树
 
区间修改、区间查询，你可能会认为，把上一章里面的这两个模块加在一起就好了，然后你就会发现你大错特错。
 
因为如果对于1~4这个区间，你把1~3区间+1，相当于把节点1~2和3标记，但是如果你查询2~4时，你会发现你加的时没有标记的2节点和没有标记的3~4节点加上去，结果当然是错的。
 
那么我们应该怎么办？这时候pushdown的作用就显现出来了。
 
你会想到，我们只需要在查询的时候，如果我们要查的2节点在1~2区间的里面，那我们就可以把1~2区间标记的那个+1给推下去这样就能顺利地加上了。
 怎么记录这个标记呢？我们需要记录一个“懒标记”lazytage，来记录这个区间
 
区间修改的时候，我们按照如下原则：
 
1、如果当前区间被完全覆盖在目标区间里，讲这个区间的sum+k*(tree[i].r-tree[i].l+1)

2、如果没有完全覆盖，则先下传懒标记

3、如果这个区间的左儿子和目标区间有交集，那么搜索左儿子

4、如果这个区间的右儿子和目标区间有交集，那么搜索右儿子
 
然后查询的时候，将这个懒标记下传就好了，下面图解一下：
 
如图，区间1-4分别是1、2、3、4，我们要把1-3区间+1。因为1~2区间被完全覆盖，所以将其+2，并将紫色的lazytage+1，3区间同理
 
 
注意我们处理完这些以后，还是要按照tree[i].sum=tree[i*2].sum+tree[i*2+1].sum的原则返回，代码如下：
 
void add(int i,int l,int r,int k)
{
    if(tree[i].r<=r && tree[i].l>=l)//如果当前区间被完全覆盖在目标区间里，讲这个区间的sum+k*(tree[i].r-tree[i].l+1)
    {
        tree[i].sum+=k*(tree[i].r-tree[i].l+1);
        tree[i].lz+=k;//记录lazytage
        return ;
    }
    push_down(i);//向下传递
    if(tree[i*2].r>=l)
        add(i*2,l,r,k);
    if(tree[i*2+1].l<=r)
        add(i*2+1,l,r,k);
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
    return ;
}
 
其中的pushdown，就是把自己的lazytage归零，并给自己的儿子加上，并让自己的儿子加上k*(r-l+1)
 
void push_down(int i)
{
    if(tree[i].lz!=0)
    {
        tree[i*2].lz+=tree[i].lz;//左右儿子分别加上父亲的lz
        tree[i*2+1].lz+=tree[i].lz;
        int mid=(tree[i].l+tree[i].r)/2;
        tree[i*2].sum+=tree[i].lz*(mid-tree[i*2].l+1);//左右分别求和加起来
        tree[i*2+1].sum+=tree[i].lz*(tree[i*2+1].r-mid);
        tree[i].lz=0;//父亲lz归零
    }
    return ;
}
 
查询的时候，和上一章的几乎一样，就是也要像修改一样加入pushdown，这里用图模拟一下。我们要查询2~4区间的和，这是查询前的情况，所有紫色的代表lazytage
 
 
然后，我们查到区间1~2时，发现这个区间并没有被完全包括在目标区间里，于是我们就pushdown，lazytage下传，并让每个区间sum加上（r-l）*lazytage。
 
 
然后查到2-2区间，发现被完全包含，所以就返3，再搜索到3~4区间，发现被完全包含，那么直接返回8，最后3+8=11就是答案
 
这里是代码实现：
 
inline int search(int i,int l,int r){
    if(tree[i].l>=l && tree[i].r<=r)
        return tree[i].sum;
    if(tree[i].r<l || tree[i].l>r)  return 0;
    push_down(i);
    int s=0;
    if(tree[i*2].r>=l)  s+=search(i*2,l,r);
    if(tree[i*2+1].l<=r)  s+=search(i*2+1,l,r);
    return s;
}
 
好了，到了这里，我们就学会了用线段树进行区间加减操作，大家可以完成洛谷的线段树模板1.
 
第四部 乘法（根号）线段树
 
1、乘法线段树
 
如果这个线段树只有乘法，那么直接加入lazytage变成乘，然后tree[i].sum*=k就好了。但是，如果我们是又加又乘，那就不一样了。
 
当lazytage下标传递的时候，我们需要考虑，是先加再乘还是先乘再加。我们只需要对lazytage做这样一个处理。
 
lazytage分为两种，分别是加法的plz和乘法的mlz。
 
mlz很简单处理，pushdown时直接*父亲的就可以了，那么加法呢？
 
我们需要把原先的plz*父亲的mlz再加上父亲的plz.
 
inline void pushdown(long long i){//注意这种级别的数据一定要开long long
    long long k1=tree[i].mlz,k2=tree[i].plz;
    tree[i<<1].sum=(tree[i<<1].sum*k1+k2*(tree[i<<1].r-tree[i<<1].l+1))%p;//
    tree[i<<1|1].sum=(tree[i<<1|1].sum*k1+k2*(tree[i<<1|1].r-tree[i<<1|1].l+1))%p;
    tree[i<<1].mlz=(tree[i<<1].mlz*k1)%p;
    tree[i<<1|1].mlz=(tree[i<<1|1].mlz*k1)%p;
    tree[i<<1].plz=(tree[i<<1].plz*k1+k2)%p;
    tree[i<<1|1].plz=(tree[i<<1|1].plz*k1+k2)%p;
    tree[i].plz=0;
    tree[i].mlz=1;
    return ;
}
 
然后加法和减法的函数同理，维护lazytage的时候加法标记一定要记得现乘再加。
 
值得一提的是，计算*2时一定要改成i<<1这样能解决很多时间，还有要开long long，还有，函数前面要加inline 我在其他OJ交这道题时，就因为没加inline 就被卡了，交了就过了。
 
2、根号线段树
 
其实，根号线段树和除法线段树一样。她们乍眼一看感觉直接用lazytage标记除了多少，但是实际上，会出现精度问题。
 
c++的除法是向下取整，很明显，(a+b)/k！=a/k+b/k（在向下取整的情况下），而根号，很明显根号（a）+根号(b)!=根号(a+b)那么怎么办？
 
第一个想法就是暴力，对于每个要改动的区间l~r,把里面的每个点都单独除，但这样就会把时间复杂度卡得比大暴力都慢（因为多个常数），所以怎么优化？
 
我们对于每个区间，维护她的最大值和最小值，然后每次修改时，如果这个区间的最大值根号和最小值的根号一样，说明这个区间整体根号不会产生误差，就直接修改（除法同理）
 
其中，lazytage把除法当成减法，记录的是这个区间里每个元素减去的值。
 
下面是根号线段树的修改过程：
 
inline void Sqrt(int i,int l,int r){
    if(tree[i].l>=l && tree[i].r<=r && (tree[i].minn-(long long)sqrt(tree[i].minn))==(tree[i].maxx-(long long)sqrt(tree[i].maxx))){//如果这个区间的最大值最小值一样
        long long u=tree[i].minn-(long long)sqrt(tree[i].minn);//计算区间中每个元素需要减去的
        tree[i].lz+=u;
        tree[i].sum-=(tree[i].r-tree[i].l+1)*u;
        tree[i].minn-=u;
        tree[i].maxx-=u;
            //cout<<"i"<<i<<" "<<tree[i].sum<<endl;
        return ;
    }
    if(tree[i].r<l || tree[i].l>r)  return ;
    push_down(i);
    if(tree[i*2].r>=l)  Sqrt(i*2,l,r);
    if(tree[i*2+1].l<=r)  Sqrt(i*2+1,l,r);
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
    tree[i].minn=min(tree[i*2].minn,tree[i*2+1].minn);//维护最大值和最小值
    tree[i].maxx=max(tree[i*2].maxx,tree[i*2+1].maxx);
    //cout<<"i"<<i<<" "<<tree[i].sum<<endl;
    return ;
}
 
然后pushdown没什么变化，就是要记得tree[i].minn、tree[i].maxx也要记得-lazytage。
 
 
附赠一份支持单点修改，区间取相反数，区间最小值，区间最大值的线段树代码
 
题目链接：https://www.luogu.com.cn/problem/P1505
 
题解：BZOJ 2157 「国家集训队」旅游（树链剖分，线段树，边权转点权）
 
struct Segment_Tree
{
	struct node 
	{
		int l, r;
		int sum;
//		int laz; 
		int tag;//相反数的tag
		int maxx;
		int minn;
	}tr[maxn << 2];
	
	void pushup(int p)
	{
		node &l = tr[p << 1], &r = tr[p << 1 | 1], &rt = tr[p];
		rt.sum = l.sum + r.sum;
		rt.maxx = max(l.maxx, r.maxx);
		rt.minn = min(l.minn, r.minn);
	}
	
	void pushdown(int p)
	{
		node &l = tr[p << 1], &r = tr[p << 1 | 1], &rt = tr[p];
		if(rt.tag == 0) return ;
		l.tag ^= 1, r.tag ^= 1;
		l.sum = -l.sum, r.sum = -r.sum;
		l.maxx = -l.maxx, r.maxx = -r.maxx;
		l.minn = -l.minn, r.minn = -r.minn;
		swap(l.maxx, l.minn), swap(r.maxx, r.minn);
		rt.tag = 0;
	}
	
	void build(int p, int l, int r)
	{
		tr[p].l = l, tr[p].r = r;
		if(l == r) {
			tr[p].sum = tr[p].minn = tr[p].maxx = a_after[l];
			return ;
		}	
		int mid = l + r >> 1;
		build(p << 1, l, mid);
		build(p << 1 | 1, mid + 1, r);
		pushup(p);
	}
	
	void modify(int p, int x, int k)
	{
		if(tr[p].l == tr[p].r) {
			tr[p].sum = tr[p].minn = tr[p].maxx = k;
			return ;
		}
		if(tr[p].tag) pushdown(p);
		int mid = tr[p].l + tr[p].r >> 1;
		if(x <= mid) modify(p << 1, x, k);
		if(x > mid) modify(p << 1 | 1, x, k);
		pushup(p);
	}
	
	void _reverse(int p, int l, int r)
	{
		if(tr[p].l >= l && tr[p].r <= r) {
			tr[p].tag ^= 1;
			tr[p].sum = -tr[p].sum;
			tr[p].minn = -tr[p].minn;
			tr[p].maxx = -tr[p].maxx;
			swap(tr[p].minn, tr[p].maxx);
			return ;
		}
		if(tr[p].tag) pushdown(p);
		int mid = tr[p].l + tr[p].r >> 1;
		if(l <= mid) _reverse(p << 1, l, r);
		if(r > mid) _reverse(p << 1 | 1, l, r);
		pushup(p);
	}
	
	int query_sum(int p, int l, int r)
	{
		int res = 0;
		if(tr[p].l >= l && tr[p].r <= r) return tr[p].sum;
		if(tr[p].tag) pushdown(p);
		int mid = tr[p].l + tr[p].r >> 1;
		if(l <= mid) res += query_sum(p << 1, l, r);
		if(r > mid) res += query_sum(p << 1 | 1, l, r);
		pushup(p);
		return res;
	}
	
	int query_max(int p, int l, int r)
	{
		int res = -INF;
		if(tr[p].l >= l && tr[p].r <= r) return tr[p].maxx;
		if(tr[p].tag) pushdown(p);
		int mid = tr[p].l + tr[p].r >> 1;
		if(l <= mid) res = max(res, query_max(p << 1, l, r));
		if(r > mid) res = max(res, query_max(p << 1 | 1, l, r));
		pushup(p);
		return res;
	}
	
	int query_min(int p, int l, int r)
	{
		int res = INF;
		if(tr[p].l >= l && tr[p].r <= r) return tr[p].minn;
		if(tr[p].tag) pushdown(p);
		int mid = tr[p].l + tr[p].r >> 1;
		if(l <= mid) res = min(res, query_min(p << 1, l, r));
		if(r > mid) res = min(res, query_min(p << 1 | 1, l, r));
		pushup(p);
		return res;
	} 
}ST; 
 
模板题与代码：
 
最后，我们给几道模板题，再贴上代码：
 
单点修改，区间查询：洛谷树状数组模板1
 
P3374 【模板】树状数组 1
 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
#define MAXN 100010
#define INF 10000009
#define MOD 10000007
#define LL long long
#define in(a) a=read()
#define REP(i,k,n) for(long long i=k;i<=n;i++)
#define DREP(i,k,n) for(long long i=k;i>=n;i--)
#define cl(a) memset(a,0,sizeof(a))
inline long long read(){
    long long x=0,f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
    return x*f;
}
inline void out(long long x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) out(x/10);
    putchar(x%10+'0');
}
long long n,m,p;
long long input[MAXN];
struct node{
    long long l,r;
    long long sum,mlz,plz;
}tree[4*MAXN];
inline void build(long long i,long long l,long long r){
    tree[i].l=l;
    tree[i].r=r;
    tree[i].mlz=1;
    if(l==r){
        tree[i].sum=input[l]%p;
        return ;
    }
    long long mid=(l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    tree[i].sum=(tree[i<<1].sum+tree[i<<1|1].sum)%p;
    return ;
}
inline void pushdown(long long i){
    long long k1=tree[i].mlz,k2=tree[i].plz;
    tree[i<<1].sum=(tree[i<<1].sum*k1+k2*(tree[i<<1].r-tree[i<<1].l+1))%p;
    tree[i<<1|1].sum=(tree[i<<1|1].sum*k1+k2*(tree[i<<1|1].r-tree[i<<1|1].l+1))%p;
    tree[i<<1].mlz=(tree[i<<1].mlz*k1)%p;
    tree[i<<1|1].mlz=(tree[i<<1|1].mlz*k1)%p;
    tree[i<<1].plz=(tree[i<<1].plz*k1+k2)%p;
    tree[i<<1|1].plz=(tree[i<<1|1].plz*k1+k2)%p;
    tree[i].plz=0;
    tree[i].mlz=1;
    return ;
}
inline void mul(long long i,long long l,long long r,long long k){
    if(tree[i].r<l || tree[i].l>r)  return ;
    if(tree[i].l>=l && tree[i].r<=r){
        tree[i].sum=(tree[i].sum*k)%p;
        tree[i].mlz=(tree[i].mlz*k)%p;
        tree[i].plz=(tree[i].plz*k)%p;
        return ;
    }
    pushdown(i);
    if(tree[i<<1].r>=l)  mul(i<<1,l,r,k);
    if(tree[i<<1|1].l<=r)  mul(i<<1|1,l,r,k);
    tree[i].sum=(tree[i<<1].sum+tree[i<<1|1].sum)%p;
    return ;
}
inline void add(long long i,long long l,long long r,long long k){
    if(tree[i].r<l || tree[i].l>r)  return ;
    if(tree[i].l>=l && tree[i].r<=r){
        tree[i].sum+=((tree[i].r-tree[i].l+1)*k)%p;
        tree[i].plz=(tree[i].plz+k)%p;
        return ;
    }
    pushdown(i);
    if(tree[i<<1].r>=l)  add(i<<1,l,r,k);
    if(tree[i<<1|1].l<=r)  add(i<<1|1,l,r,k);
    tree[i].sum=(tree[i<<1].sum+tree[i<<1|1].sum)%p;
    return ;
}
inline long long search(long long i,long long l,long long r){
    if(tree[i].r<l || tree[i].l>r)  return 0;
    if(tree[i].l>=l && tree[i].r<=r)
        return tree[i].sum;
    pushdown(i);
    long long sum=0;
    if(tree[i<<1].r>=l)  sum+=search(i<<1,l,r)%p;
    if(tree[i<<1|1].l<=r)  sum+=search(i<<1|1,l,r)%p;
    return sum%p;
}
int main(){
    in(n);    in(m);in(p);
    REP(i,1,n)  in(input[i]);
    build(1,1,n); 

    REP(i,1,m){
        long long fl,a,b,c;
        in(fl);
        if(fl==1){
            in(a);in(b);in(c);
            c%=p;
            mul(1,a,b,c);
        }
        if(fl==2){
            in(a);in(b);in(c);
            c%=p;
            add(1,a,b,c);
        }
        if(fl==3){
            in(a);in(b);
            printf("%lld\n",search(1,a,b));
        }
    }
    return 0;
}
/*
5 4 1000
1 2 3 4 5
3 1 5
2 1 5 1
1 1 5 2

3 1 5
*/ 
 
区间修改，单点查询：洛谷树状数组模板2
 
P3368 【模板】树状数组 2
 
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
int n,m;
int ans;
int input[500010];
struct node
{
    int left,right;
    int num;
}tree[2000010];
void build(int left,int right,int index)
{
    tree[index].num=0;
    tree[index].left=left;
    tree[index].right=right;
       if(left==right)
        return ;
    int mid=(right+left)/2;
    build(left,mid,index*2);
    build(mid+1,right,index*2+1);
}
void pls(int index,int l,int r,int k)
{
    if(tree[index].left>=l && tree[index].right<=r)
    {
        tree[index].num+=k;
        return ;
    }
    if(tree[index*2].right>=l)
       pls(index*2,l,r,k);
    if(tree[index*2+1].left<=r)
       pls(index*2+1,l,r,k);
}
void search(int index,int dis)
{
    ans+=tree[index].num;
    if(tree[index].left==tree[index].right)
        return ;
    if(dis<=tree[index*2].right)
        search(index*2,dis);
    if(dis>=tree[index*2+1].left)
        search(index*2+1,dis);
}
int main()
{
    int n,m;
    cin>>n>>m;
    build(1,n,1);
    for(int i=1;i<=n;i++)
        scanf("%d",&input[i]);
    for(int i=1;i<=m;i++)
    {
        int a;
        scanf("%d",&a);
        if(a==1)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            pls(1,x,y,z);
        }
        if(a==2)
        {
            ans=0;
            int x;
            scanf("%d",&x);
            search(1,x);
            printf("%d\n",ans+input[x]);
        }
    }
}
 
区间加法，洛谷线段树模板1
 
P3372 【模板】线段树 1
 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+7;
const ll mod=2147483647;
ll n,m;
struct node
{
    ll l,r,sum,lz;
}tree[N];
ll arr[N];
void build(ll i,ll l,ll r,ll arr[])
{
    tree[i].lz=0;//初始化的时候肯定都是0
    tree[i].l=l;
    tree[i].r=r;
    if(l==r)
    {
        tree[i].sum=arr[l];//到达底部单节点才把输入的值赋给你
        return ;
    }
    ll mid=(l+r)/2;
    build(i*2,l,mid,arr);
    build(i*2+1,mid+1,r,arr);
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;//树已经全部建完了，再从下往上+++，使得上层的树都有了值
    return ;
}
inline void push_down(ll i)
{
    if(tree[i].lz!=0)
    {
        tree[i*2].lz+=tree[i].lz;
        tree[i*2+1].lz+=tree[i].lz;
        ll mid=(tree[i].l+tree[i].r)/2;
        tree[i*2].sum+=tree[i].lz*(mid-tree[i*2].l+1);
        tree[i*2+1].sum+=tree[i].lz*(tree[i*2+1].r-mid);
        tree[i].lz=0;
    }
    return ;
}
inline void add(ll i,ll l,ll r,ll k)
{
    if(tree[i].l>=l&&tree[i].r<=r)
    {
        tree[i].sum+=k*(tree[i].r-tree[i].l+1);
        tree[i].lz+=k;
        return ;
    }
    push_down(i);
    if(tree[i*2].r>=l)
        add(i*2,l,r,k);
    if(tree[i*2+1].l<=r)
        add(i*2+1,l,r,k);
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
    return ;
}
inline ll searchs(ll i,ll l, ll r)
{
    if(tree[i].l>=l&&tree[i].r<=r)
        return tree[i].sum;
    push_down(i);
    ll num=0;
    if(tree[i*2].r>=l)
        num+=searchs(i*2,l,r);
    if(tree[i*2+1].l<=r)
        num+=searchs(i*2+1,l,r);
    return num;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i)
        cin>>arr[i];
    build(1,1,n,arr);//从根节点开始建树
    for(int i=1;i<=m;++i)
    {
        ll tmp;
        cin>>tmp;
        if(tmp==1)
        {
            ll a,b,c;
            cin>>a>>b>>c;
            add(1,a,b,c);//每次修改都是从编号为1开始的，因为编号1是树的顶端，往下分叉
        }
        if(tmp==2)
        {
            ll a,b;
            cin>>a>>b;
            printf("%lld\n",searchs(1,a,b));//编号i的话，每次都是从1开始
        }
    }
    return 0;
}
 
区间乘法：洛谷线段树模板2
 
P3373 【模板】线段树 2
 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+7;
template<typename T>void read(T &x)
{
    x=0;char ch=getchar();ll f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}x*=f;
}
ll n,m,arr[N],mod,flag,cn,cm,cw;
struct node
{
    ll l,r,sum,mul,add;//有乘有加，先乘后加
}tree[N];

inline void build(ll i,ll l,ll r)
{
    tree[i].l=l;
    tree[i].r=r;
    tree[i].mul=1;
    if(l==r)
    {
        tree[i].sum=arr[l]%mod;
        return ;
    }
    ll mid=(l+r)>>1;
    build(i*2,l,mid);
    build(i*2+1,mid+1,r);
    tree[i].sum=(tree[i*2].sum+tree[i*2+1].sum)%mod;
}
inline void push_down(ll i)
{
    tree[i*2].sum=(ll)(tree[i].mul*tree[i*2].sum+((tree[i*2].r-tree[i*2].l+1)*tree[i].add)%mod)%mod;
    tree[i*2+1].sum=(ll)(tree[i].mul*tree[i*2+1].sum+((tree[i*2+1].r-tree[i*2+1].l+1)*tree[i].add)%mod)%mod;
    tree[i*2].mul=(ll)(tree[i*2].mul*tree[i].mul)%mod;
    tree[i*2+1].mul=(ll)(tree[i*2+1].mul*tree[i].mul)%mod;
    tree[i*2].add=(ll)(tree[i*2].add*tree[i].mul+tree[i].add)%mod;
    tree[i*2+1].add=(ll)(tree[i*2+1].add*tree[i].mul+tree[i].add)%mod;
    tree[i].mul=1;tree[i].add=0;
}
inline void add(ll i,ll l,ll r,ll k)
{
    if(tree[i].l>=l&&tree[i].r<=r)
    {
        tree[i].add=(ll)(tree[i].add+k)%mod;
        tree[i].sum=(ll)(tree[i].sum+k*(tree[i].r-tree[i].l+1))%mod;
        return ;
    }
    push_down(i);
  
    if(tree[i*2].r>=l)
        add(i*2,l,r,k);
    if(tree[i*2+1].l<=r)
        add(i*2+1,l,r,k);
    //ll mid=(tree[i].l+tree[i].r)>>1;
    //if(l<=mid)add(i*2,l,r,k);
    //if(mid<r)add(i*2+1,l,r,k);
    tree[i].sum=(tree[i*2].sum+tree[i*2+1].sum)%mod;
}
inline void mult(ll i,ll l,ll r,ll k)
{
    if(tree[i].l>=l&&tree[i].r<=r)
    {
        tree[i].mul=(tree[i].mul*k)%mod;
        tree[i].add=(tree[i].add*k)%mod;
        tree[i].sum=(tree[i].sum*k)%mod;
        return ;
    }
    push_down(i);
  
    if(tree[i*2].r>=l)
        mult(i*2,l,r,k);
    if(tree[i*2+1].l<=r)
        mult(i*2+1,l,r,k);
    //ll mid=(tree[i].l+tree[i].r)>>1;
    //if(l<=mid)mult(i*2,l,r,k);
    //if(mid<r)mult(i*2+1,l,r,k);
    tree[i].sum=(tree[i*2].sum+tree[i*2+1].sum)%mod;
}
inline ll query(ll i,ll l,ll r)
{
    if(tree[i].l>=l&&tree[i].r<=r)
        return tree[i].sum;
    push_down(i);
    ll num=0;
    if(tree[i*2].r>=l)
        num=(num+query(i*2,l,r))%mod;
    if(tree[i*2+1].l<=r)
        num=(num+query(i*2+1,l,r))%mod;
    return num;
    //ll val=0;
    //ll mid=(tree[i].l+tree[i].r)>>1;
    //if(l<=mid)val=(val+query(i*2,l,r))%mod;
    //if(mid<r)val=(val+query(i*2+1,l,r))%mod;
    //return val;
}
int main()
{
    read(n),read(m),read(mod);
    for(int i=1;i<=n;++i)
        read(arr[i]);
    build(1,1,n);
    for(int i=1;i<=m;++i)
    {
        read(flag);
        if(flag==1)
        {
            read(cn),read(cm),read(cw);
            mult(1,cn,cm,cw);
        }
        else if(flag==2){
            read(cn),read(cm),read(cw);
            add(1,cn,cm,cw);
        }
        else {
            read(cn),read(cm);
            cout<<query(1,cn,cm)<<endl;
        }
    }
}
/*
5 4 1000
1 2 3 4 5
3 1 5
2 1 5 1
1 1 5 2

3 1 5
*/ 
 
区间根号，bzoj3211
 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define MAXN 1000010
#define REP(i,k,n) for(int i=k;i<=n;i++)
#define in(a) a=read()
using namespace std;
int read(){
    int x=0,f=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar())
        if(ch=='-')
          f=-1;
    for(;isdigit(ch);ch=getchar())
        x=x*10+ch-'0';
    return x*f;
}
struct node{
    int l,r;
    long long lz,sum,maxx,minn;
}tree[MAXN<<2];
int n,m,input[MAXN];
inline void build(int i,int l,int r){
    tree[i].l=l;tree[i].r=r;
    if(l==r){
        tree[i].sum=tree[i].minn=tree[i].maxx=input[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(i*2,l,mid);
    build(i*2+1,mid+1,r);
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
    tree[i].minn=min(tree[i*2].minn,tree[i*2+1].minn);
    tree[i].maxx=max(tree[i*2].maxx,tree[i*2+1].maxx);
    return ;
}
inline void push_down(int i){
    if(!tree[i].lz)  return ;
    long long k=tree[i].lz;
    tree[i*2].lz+=k;
    tree[i*2+1].lz+=k;
    tree[i*2].sum-=(tree[i*2].r-tree[i*2].l+1)*k;
    tree[i*2+1].sum-=(tree[i*2+1].r-tree[i*2+1].l+1)*k;
    tree[i*2].minn-=k;
    tree[i*2+1].minn-=k;
    tree[i*2].maxx-=k;
    tree[i*2+1].maxx-=k;
    tree[i].lz=0;
    return ;
}
inline void Sqrt(int i,int l,int r){
    if(tree[i].l>=l && tree[i].r<=r && (tree[i].minn-(long long)sqrt(tree[i].minn))==(tree[i].maxx-(long long)sqrt(tree[i].maxx))){
        long long u=tree[i].minn-(long long)sqrt(tree[i].minn);
        tree[i].lz+=u;
        tree[i].sum-=(tree[i].r-tree[i].l+1)*u;
        tree[i].minn-=u;
        tree[i].maxx-=u;
            //cout<<"i"<<i<<" "<<tree[i].sum<<endl;
        return ;
    }
    if(tree[i].r<l || tree[i].l>r)  return ;
    push_down(i);
    if(tree[i*2].r>=l)  Sqrt(i*2,l,r);
    if(tree[i*2+1].l<=r)  Sqrt(i*2+1,l,r);
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
    tree[i].minn=min(tree[i*2].minn,tree[i*2+1].minn);
    tree[i].maxx=max(tree[i*2].maxx,tree[i*2+1].maxx);
    //cout<<"i"<<i<<" "<<tree[i].sum<<endl;
    return ;
}
inline long long search(int i,int l,int r){
    if(tree[i].l>=l && tree[i].r<=r)
        return tree[i].sum;
    if(tree[i].r<l || tree[i].l>r)  return 0;
    push_down(i);
    long long s=0;
    if(tree[i*2].r>=l)  s+=search(i*2,l,r);
    if(tree[i*2+1].l<=r)  s+=search(i*2+1,l,r);
    return s;
}
int main(){
    in(n);
    REP(i,1,n)  in(input[i]);
    build(1,1,n);
    in(m);
    int a,b,c;
    REP(i,1,m){
        in(a);in(b);in(c);
        if(a==1)
            printf("%lld\n",search(1,b,c));
        if(a==2){
            Sqrt(1,b,c);
            //for(int i=1;i<=7;i++)
            //    cout<<tree[i].sum<<" ";
           // cout<<endl;
        }
    }
}
 
这一篇文章讲解的非常详细易懂，所以存下来用来复习。
 对原作者的图进行了重画，更加清晰，对排版也做了优化。
 后面的模板代码也用的是我自己AC的代码。
 注：如果您通过本文,有(qi)用(guai)的知识增加了，请您点个赞再离开,如果不嫌弃的话,点个关注再走吧 ! 当然，也欢迎在讨论区指出此文的不足处，作者会及时对文章加以修正 !

 
文章目录
 
1 线段树介绍
1.1 线段树的结构及性质
1.2 建树
  
2 区间查询
3 单点更新
4 区间更新
5 线段树的优缺点
后记

 
1 线段树介绍
 
  线段树，我刚开始听到这个名字的时候，感觉就是高大上，怕难度会很大，但是实际学起来的时候，会发现还是挺好理解的，很亲民→_→
   扯远了，先盗个图抛个问题：
 
   图中的RMQ指的是(Range Minimum Query)问题(区间最值查询)。按暴力法直接一个for循环过去查询，每次查询的时间复杂度为O(N)，频繁查询就是O(MN)了，性能上肯定要爆炸，代码要是这样写，分分钟被leader扔下楼。。。
   线段树主要就是用于频繁的区间查询、区间更新，区间查询、更新的时间复杂度是O(logN)，是典型的以空间换时间。
 
1.1 线段树的结构及性质
 
  以长度为5的区间为例，线段树的结构如下图所示。其中圆框内表示该节点所管理的区间，红色字体表示节点id。例如，根节点的节点id是1，它管理的区间范围为[1, 5]。
 
   从图中可以看出线段树的几个性质：
 
线段树的每个节点维护一个区间[i, j]的信息。如果一个节点维护着区间[i, j]的信息，且i != j，那么其左孩子维护着区间[i, (i+j)/2]的信息，右孩子维护着区间[(i+j)/2+1, j]的信息。
线段树中，如果一个节点的编号为x，那么左孩子的编号为2x，右孩子的编号为2x+1。
N个元素的线段树的高度为logN+1
 
  线段树常用静态数组进行存储。数组长度通常开最大长度的4倍，不然很容易出现数组越界程序core掉。
 
1.2 建树
 
  为了方便理解，这里使用一个简单的小例子来描述建树的过程。
   对于原始数组：A = {1, 5, 8, 2, 90}，我们用这个数组来建立线段树，用于查询区间的最小值。实际上建树过程就是建立普通二叉树的先序建树，如下图所示。图中的[x, y]:z表示x, y是区间端点，z是该区间的最小值。
   对于每个父节点，建立完其左右子节点后，父节点的最小值 = min(左节点的最小值, 右节点的最小值)，自底向上求出每个节点所对应的区间的最小值。
 
   建树的代码也很简洁，采用递归实现：
 
/**
 * 递归创建线段树
 * 参数：viData 初始数据
 * 参数：dwNodeId 当前构造的线段树节点id
 * 参数：dwLeft 当前构造的线段树节点管理的左区间（闭区间）
 * 参数：dwRight 当前构造的线段树节点管理的右区间（闭区间）
 */
void Build(const std::vector<int>& viData, uint32_t dwNodeId
				, uint32_t dwLeft, uint32_t dwRight)
{
	if (dwLeft == dwRight)	// 叶子节点
	{
		m_viMin[dwNodeId] = viData[dwLeft];
		return;
	}

	uint32_t dwMid = (dwLeft + dwRight) >> 1;
	Build(viData, dwNodeId << 1, dwLeft, dwMid);	// 左子树
	Build(viData, dwNodeId << 1 | 1, dwMid + 1, dwRight);	// 右子树
	// 更新当前节点的最小值
	m_viMin[dwNodeId] = std::min(m_viMin[dwNodeId << 1], m_viMin[dwNodeId << 1 | 1]);
}
 
  计算左右节点id，我这边是习惯用位运算 dwNodeId << 1 替换 2 * dwNodeId，用 dwNodeId << 1 | 1 替换 2 * dwNodeId + 1，因为位运算的效率要高一些。
 
2 区间查询
 
  在刚才建好的线段树上查询RMQ(3, 5)，查询过程如下图所示：
 
   首先从根节点开始查询，发现根节点的区间[1, 5]有部分不符合查询区间[3, 5]，向下查询其左右子区间，直到找出一个节点的区间能够完全被查询区间包围为止，即图中的[3, 3]及[4, 5]区间，此时就不需要再继续往下查询了。
   得到子区间的RMQ值后，返回给父亲节点，父亲节点再从返回的2个子区间的RMQ值中取一个小的return给其父亲，层层返回，最后得到所要求区间的RMQ值。
 
代码如下：
 
/**
 * 区间查询
 * 参数：dwNodeId 当前查询的线段树节点id
 * 参数：dwNodeLeft 当前查询的线段树节点管理的左区间（闭区间）
 * 参数：dwNodeRight 当前查询的线段树节点管理的右区间（闭区间）
 * 参数：dwQueryLeft 所要查询的左区间（闭区间）
 * 参数：dwQueryRight 所要查询的右区间（闭区间）
 * 返回值：查询到的最小值，INF表示无穷大，意味着查询结果不存在
 */
int Query(uint32_t dwNodeId, uint32_t dwNodeLeft, uint32_t dwNodeRight
			, uint32_t dwQueryLeft, uint32_t dwQueryRIght)
{
	// 查询区间与线段树节点管理的区间无交集，结束查询
	if (dwQueryLeft > dwNodeRight || dwQueryRight < dwNodeLeft)
		return INF;
	// 当前节点管理的区间完全被查询区间包含，直接返回
	if (dwQueryLeft <= dwNodeLeft && dwQueryRight >= dwNodeRight)
		return m_viMin[dwNodeId];
	
	// 递归查询左右子树
	uint32_t dwMid = (dwNodeLeft + dwNodeRight) >> 1;
	int iRetLeft = Query(dwNodeId << 1, dwNodeLeft, dwMid
									, dwQueryLeft, dwQueryRight);
	int iRetRight = Query(dwNodeId << 1 | 1, dwMid + 1, dwNodeRIght
									, dwQueryLeft, dwQueryRight);
	return std::min(iRetLeft, iRetRight);
}
 
从代码可以推算得出，线段树区间查询的时间复杂度为O(logN)。
 
3 单点更新
 
  只有查询当然不可能啦，总会需要更新节点信息的，那么首先就先讲一下单点更新。
   还是以刚才那颗线段树为例子。例如要修改A[2]为0，那么首先从根节点开始往下找，找到区间为[2, 2]的节点之后，将它的最小值更新为0，之后向上递归更新各个父节点的最小值。过程如下图所示：
 
   自顶向下找到对应节点后，修改其值，并原路返回，自底向上更新所经过的各区间RMQ值。
   显然，每次更新修改不超过logN个节点的信息。
 
代码如下：
 
/**
 * 单点更新
 * 参数：dwNodeId 当前更新的线段树节点id
 * 参数：dwNodeLeft 当前更新的线段树节点管理的左区间（闭区间）
 * 参数：dwNodeRight 当前更新的线段树节点管理的右区间（闭区间）
 * 参数：dwUpdateId 所要更新的数据节点id
 * 参数：iVal 所要更新的数据值
 */
void Update(uint32_t dwNodeId, uint32_t dwNodeLeft, uint32_t dwNodeRight
					, uint32_t dwUpdateId, int iVal)
{
	// 更新点id不在当前线段树节点管理的区间中，结束更新
	if (dwUpdateId < dwNodeLeft || dwUpdateId > dwNodeRight) return;

	if (dwNodeLeft == dwNodeRight && dwNodeLeft == dwUpdateId)
	{
		// 找到所要更新的节点
		m_viMin[dwNodeId] = iVal;
		return;
	}

	// 递归更新左右子树
	uint32_t dwMid = (dwNodeLeft + dwNodeRight) >> 1;
	Update(dwNodeId << 1, dwNodeLeft, dwMid, dwUpdateId, iVal);
	Update(dwNodeId << 1 | 1, dwMid + 1, dwNodeRight, dwUpdateId, iVal);
	// 更新当前节点的最小值
	m_viMin[dwNodeId] = std::min(m_viMin[dwNodeId << 1], m_viMin[dwNodeId << 1 | 1]);
}
 
  从代码可以推算得出，线段树单点更新的时间复杂度为O(logN)。
 
4 区间更新
 
  上面讲完了区间查询、单点更新之后，是不是就没了咧？当然不是，线段树可不是这么简陋就完事了的。实际问题中，总会需要进行区间更新的，如果是把区间拆开分别调用单点更新，那么每次区间更新的时间复杂度就是O(NlogN)，要是区间更新的操作频繁一点的话，那就是O(NMlogN)，分分钟想哭。
   于是咧，就要开始讲线段树的精华所在——延迟标记。
   延迟标记是指对每个节点新增加一个标记，记录这个节点是否进行了某种修改(这种修改操作会影响其子节点)。
 
   对于一段区间[L,R]的更新，先按照之前方法递归下去，直到遇到一个节点所管辖区间完全被[L,R]包含的节点时，我们只需要更新此节点，然后在此处做上一个延迟标记 add[x]=val 表示该节点下所有子节点都被加了一个值val，此时即可结束更新过程。
 
在这里大家可能会有个疑问，为什么做了延迟标记后就可以终止更新呢？
   假设当前节点管辖区间为[L,R]。打下延迟标记时，已经修正了 sum[L_R]的值，后续的查询或更新操作可能只访问到当前节点而不需要知道其子区间的sum值。因此，不必去更新其子区间的值。
   而当我们需要查询或更新区间[L,R]的子区间时（例如[L,mid]），此时我们才需要把标记传递到儿子节点，并更新他们所管辖左右子区间的值。
   这也就是延迟标记这个名字的由来（我猜的哈）。对于暂时不需要碰到的区间，我只在它的父节点上打个标记，迟一些需要操作这个区间了再来处理之前打过的标。
 
  因为是区间更新，所以这回换个例子，不用那个区间最小值的线段树做例子，改为区间求和的线段树。
   要对区间[1, 4]的值都加上5，那么就向下查找出能够完全被区间[1, 4]包围的节点，即图中的[1, 3]和[4, 4]。然后给这两个节点打上延迟标记，并维护当前区间的区间和，至于它们的子区间就不去管了。
 
   之后，查询区间[3, 3]的区间和，那么在查询到[3, 3]之前，会先查到[1, 3]这个区间，由于需要查询[1, 3]的子区间，所以将区间[1, 3]的延迟标记下方到它的子区间[1, 2]和[3, 3]，并维护这两个子区间的区间和，并清除区间[1, 3]的延迟标记。最后才往下查询，找到区间[3, 3]，并返回它的区间和。
 
   总结起来就是，先按照区间查询、单点更新的方法处理当前区间, 当需要访问当前区间的子区间时，则先下放延迟标记(并清除自身标记) ，再递归到子区间进行更新或查询操作。
   按照刚才的描述，那么区间更新其实就分为两部分：下放延迟标记 和 更新节点。
   下放延迟标记的代码如下：
 
/**
 * 下放延迟标记（并清除自身标记）
 * 参数：dwNodeId 当前处理的线段树节点id
 * 参数：dwLeft 当前处理的线段树节点管理的左区间（闭区间）
 * 参数：dwRight 当前处理的线段树节点管理的右区间（闭区间）
 */
void PushDown(uint32_t dwNodeId, uint32_t dwLeft, uint32_t dwRight)
{
	// 无延迟标记，结束
	if (0 == m_viAdd[dwNodeId]) return;
	// 将延迟标记下放到左右子树，并修正左右子树的sum值
	uint32_t dwMid = (dwLeft + dwRight) >> 1;
	m_viAdd[dwNodeId << 1] += m_viAdd[dwNodeId];
	m_viSum[dwNodeId << 1] += (dwMid - dwLeft + 1) * m_viAdd[dwNodeId];
	m_viAdd[dwNodeId << 1 | 1] += m_viAdd[dwNodeId];
	m_viSum[dwNodeId << 1 | 1] += (dwRight - dwMid) * m_viAdd[dwNodeId];
	// 清除自身标记
	m_viAdd[dwNodeId] = 0;
}
 
  区间更新的代码如下：
 
/**
 * 区间更新
 * 参数：dwNodeId 当前更新的线段树节点id
 * 参数：dwNodeLeft 当前更新的线段树节点管理的左区间（闭区间）
 * 参数：dwNodeRIght 当前更新的线段树节点管理的右区间（闭区间）
 * 参数：dwUpdateLeft 所要更新的左区间（闭区间）
 * 参数：dwUpdateRight 所要更新的右区间（闭区间）
 * 参数：iVal 所要更新的数据值
 */
void Update(uint32_t dwNodeId, uint32_t dwNodeLeft, uint32_t dwNodeRight
					, uint32_t dwUpdateLeft, uint32_t dwUpdateRight, int iVal)
{
	// 更新点id不在当前线段树节点管理的区间中，结束更新
	if (dwUpdateRight < dwNodeLeft || dwUpdateLeft > dwNodeRight) return;

	if (dwUpdateLeft <= dwNodeLeft && dwUpdateRight >= dwNodeRight)
	{
		// 当前节点管理的区间完全被更新区间包含，更新sum，打上延迟标记，结束更新
		m_viSum[dwNodeId] += (dwNodeRight - dwNodeLeft + 1) * iVal;
		m_viAdd[dwNodeId] += iVal;
		return;
	}

	PushDown(dwNodeId, dwNodeLeft, dwNodeRight);	// 下放延迟标记
	// 递归更新左右子树
	uint32_t dwMid = (dwNodeLeft + dwNodeRight) >> 1;
	Update(dwNodeId << 1, dwNodeLeft, dwMid, dwUpdateLeft, dwUpdateRight, iVal);
	Update(dwNodeId << 1 | 1, dwMid + 1, dwNodeRight, dwUpdateLeft, dwUpdateRight, iVal);
	// 更新当前节点的区间和
	m_viSum[dwNodeId] = m_viSum[dwNodeId << 1] + m_viSum[dwNodeId << 1 | 1];
}
 
  可以发现，和单点更新相比，几乎只多了一步PushDown处理延迟标记 ，其余地方的处理方法几乎一样。
   使用延迟标记，让线段树区间更新的时间复杂度变为O(logN)
 
  到这里，线段树的内容就讲完了 才没完呢。刚才说了，使用延迟标记之后，当查询、更新子区间的时候，需要下放延迟标记。所以呢，前面区间查询的代码也需要小改一下：
 
/**
 * 区间查询
 * 参数：dwNodeId 当前查询的线段树节点id
 * 参数：dwNodeLeft 当前查询的线段树节点管理的左区间（闭区间）
 * 参数：dwNodeRight 当前查询的线段树节点管理的右区间（闭区间）
 * 参数：dwQueryLeft 所要查询的左区间（闭区间）
 * 参数：dwQueryRight 所要查询的右区间（闭区间）
 * 返回值：查询结果
 */
int Query(uint32_t dwNodeId, uint32_t dwNodeLeft, uint32_t dwNodeRight
				, uint32_t dwQueryLeft, uint32_t dwQueryRight)
{
	// 查询区间与当前线段树节点管理的区间无交集，结束查询
	if (dwQueryLeft > dwNodeRight || dwQueryRight < dwNodeLeft)
		return 0;

	// 当前节点管理的区间完全被查询区间包含，直接返回
	if (dwQueryLeft <= dwNodeLeft && dwQueryRight >= dwNodeRight)
		return m_viSum[dwNodeId];

	PushDown(dwNodeId, dwNodeLeft, dwNodeRight);	// 下放延迟标记
	// 递归查询左右子树
	uint32_t dwMid = (dwNodeLeft + dwNodeRight) >> 1;
	int iRetLeft = Query(dwNodeId << 1, dwNodeLeft, dwMid, dwQueryLeft, dwQueryRight);
	int iRetRight = Query(dwNodeId << 1 | 1, dwMid + 1, dwNodeRight, dwQueryLeft, dwQueryRight);
	return iRetLeft + iRetRight;
}
 
  和之前的区间查询相比，几乎只多了一步PushDown处理延迟标记 ，其余地方的处理方法和之前几乎一样。时间复杂度依旧是O(logN)。
 
5 线段树的优缺点
 
  优点
 
区间查询、区间更新的时间复杂度为O(log N)
延迟标记的思想
代码简洁，实现方便
 
  缺点
 
不支持区间插入、删除，每次修改区间范围都需要重新建树，性能会降很多
所解决的问题需要能划分成子问题来处理
需要较大的额外空间来存放线段树，一般需要开4N的空间
 
  前两个缺点比较致命，不符合那两点要求的场景，线段树都不适用。 然而符合这两点要求的，大部分都只存在于算法竞赛或者笔试面试题中。。。Orz（也可能是因为我太菜，还没接触到或者联想起来。。。Orz）
 
 
后记
 
  到这里，线段树的基本介绍就差不多说完了，准备下一篇博客讲一下线段树的应用。
   其实为什么突然翻出线段树来讲呢？因为自从学了线段树以来，一直都是用来打ACM或者是刷笔试面试编程题，由于线段树那两个致命缺陷，我也没有想出线段树能在实际应用中用在哪个地方。直到最近在公司有同学分享了一下STL的内存分配，给了我灵感：线段树是不是可以用于内存管理？ 对于固定的一片内存区域，在其中进行内存分配、内存释放，其实这些也属于区间操作。想到这，两眼就放光。简单的代码差不多撸完了，这几天再写篇新的博客来记录一下思路和过程，也欢迎各位大佬的指点。

一.基本概念
 
1.线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。
 
 
 
（严格来说：二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。所以呢，线段树严格来说并不能算是，但是广义上的二叉查找树只需满足既是二叉树，又可以支持一些搜索操作…emmm，随意一点。还有人说线段树是一种完全二叉树，严格来看，完全二叉树需要最后一层节点都在最左侧，emmm，线段树也不符合，不过很多人都说是完全二叉树，你们就按不严格的来看吧，笑哭~ 还是平衡二叉树最符合了的说~）
 
 
2.优点 
 当我们需要对【1，n】范围内的任一区间【l，r】进行修改和求区间和，很明显暴力是一定会t的，所以我们需要将每个区间都提前保存下来，需要改哪个我们就改哪个。
 
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。而未优化的空间复杂度为2N，实际应用时一般还要开4N的数组以免越界，因此有时需要离散化让空间压缩。
 
 
 
为什么要开四倍的数组呢~ 
 线段树是一棵二叉树，最底层有n个叶子节点（n为区间大小） 
 那么由此可知，此二叉树的高度为,可证 
 然后通过等比数列求和求得二叉树的节点个数，具体公式为，（x为树的层数，为树的高度+1）
 
 
化简可得,整理之后即为（近似计算忽略掉-1） 
 证毕 
 证明来自：https://blog.csdn.net/smoggyxhdz/article/details/78895672
 
 
3.实现 
 每个节点以结构体的方式存储，结构体包含以下几个信息： 
 （1） 区间左端点、右端点；（这两者必有） 
 （2）这个区间要维护的信息（事实际情况而定，数目不等）。 
 （3）延时标记（或懒标记），当节点信息修改后由于在查询时没有用到该区间，所以没必要对该区间即以下区间进行修改，延时标记就是干这个用的，等用的时候在向下进行区间修改，不然我就卡在这~略略略~
 
4、线段树的基本思想：二分。
 
5.线段树基本形式 
 
 
（1）每个节点的左孩子区间范围为[l，mid]，右孩子为[mid+1,r] 
 （2）对于结点k，左孩子结点为2*k，右孩子为2*k+1，
 
二.线段树基本操作
 
0.定义
 
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
const int N = 1000 + 10;
//用位运算速度快
int x, y, ans, s, a, b;
 
1.结构体形式
 
struct node
{
    int l, r, w, mark;//记录左孩子，右孩子，区间和，还有延时标记
}tree[N<<2];
 
2.建树 
 思路 
 a、确定每次二分到的节点的左右端点，确定该节点存的左右范围。 
 b、如果是叶子节点，存储要维护的信息。 
 c、状态合并，计算父节点的区间和。
 
void build(int l, int r, int rt)//l,r表示当前节点区间，rt表示当前节点编号
{
    tree[rt].l = l; tree[rt].r = r;
    if(l == r){//说明到达叶子节点
        scanf("%d", &tree[rt].w);
        return;
    }
    int m = (l+r)/2;//二分
    build(ls);//建立左子树
    build(rs);//建立右子树
    tree[rt].w = tree[rt<<1].w + tree[rt<<1|1].w;
    //状态合并，此结点的w=两个孩子的w之和 
}
 
3.延时标记下传 
 这里以给区间[a,b]的每个数都加x为例讲解~ 
 思路（重点）： 
 a.递归到这个节点时，只更新这个节点的状态，并把当前的更改值累积到标记中。注意是累积，可以这样理解：过年，很多个亲戚都给你压岁钱，但你暂时不用，所以都被你父母扣下了。
 
b.当需要递归这个节点的子节点时，延时标记下传给子节点。
 
c.下传操作：
 
3部分： 
 ①将当前节点的延时标记分别累积到子节点的延时标记中。
 
②修改子节点状态。即子节点原状态+子节点区间点的个数*父节点传下来的延时标记。
 
注意不能乘自己的延时标记：
 
因为自己的标记可能是父节点多次传下来的累积，每次都乘自己的懒标记造成重复累积
 
③父节点懒标记清0。这个懒标记已经传下去了，不清0后面再用这个懒标记时会重复下传。就像你父母给了你5元钱，你不能说因为前几次给了你10元钱, 所以这次给了你15元，那你不就亏大了。 
 
void down(int rt)//标记下传 
{
    tree[rt<<1].mark += tree[rt].mark;
    tree[rt<<1|1].mark += tree[rt].mark;
    tree[rt<<1].w += tree[rt].mark*(tree[rt<<1].r-tree[rt<<1].l+1);
    tree[rt<<1|1].w += tree[rt].f*(tree[rt<<2|1].r-tree[rt<<2+1].l+1);
    tree[rt].f = 0;
}
 
4.单点查询，即查询一个点的状态，设待查询点为x 
 思路： 
 （1）如果当前枚举的点左右端点相等，即叶子节点，就是目标节点。 
 （2）如果不是，利用二分法,设查询位置为x，当前结点区间范围为【l，r】，设中点为m，则如果x<=m，则递归它的左孩子，否则递归它的右孩子
 
void ask_poi(int rt)//rt表示当前节点编号 单点查询
{
    if(tree[rt].l == tree[rt].r)//当该结点的左右端点相等，是叶子节点，是最终答案
    {
        ans = tree[rt].w;
        return;
    }
    if(tree[rt].mark)   down(rt);//懒标志下传
    int m = (tree[rt].l + tree[rt].r)/2;
    if(x <= m)
        ask_poi(rt<<1);//目标位置比中点靠左,就递归左孩子
    else
        ask_poi(rt<<1|1);//反之,递归右孩子
}
 
5.单点修改，即更改某一个点的状态 
 思路 
 找到x的位置；根据建树状态合并的原理，修改每个结点的状态。当不需要用到该节点时，可以先不更改，先用延时标记保存在父节点上
 
void change_poi(int rt)//rt表示当前节点编号 单点修改
{
    if(tree[rt].l == tree[rt].r)//找到目标位置
    {
        tree[rt].w += s;
        return;
    }
    if(tree[rt].mark)   down(rt);
    int m = (tree[rt].l + tree[rt].r)/2;
    if(x<=m)    change_poi(rt<<1);
    else    change_poi(rt<<1|1);
    tree[rt].w = tree[rt<<1].w + tree[rt<<1|1].w;
}
 
6.区间查询，，即查询一段区间的状态 
 思路 
 a.当当前区域的值全是所需答案区域的值得一部分，就直接加上当前区域 
 b.当当前区域只有一部分是答案，则暂时不加，继续通过二分递归，直到是答案的一部分 
 c.当当前区域包含了答案区域，继续二分，直到是答案的一部分停止
 
mid=(l+r)/2 
 y<=mid ,即 查询区间全在，当前区间的左子区间，往左孩子走 
 x>mid 即 查询区间全在，当前区间的右子区间，往右孩子走 
 否则，两个子区间都走
 
void ask_interval(int rt)//区间查询
{
    if(tree[rt].l >= a && tree[rt].r <=b)
    {
        ans += tree[rt].w;
        return;
    }
    if(tree[rt].mark)   down(rt);
    int m = (tree[rt].l + tree[rt].r)/2;
    if(a <= m)  ask_interval(rt<<1);
    if(b > m)   ask_interval(rt<<1|1);
}
 
7.区间修改，即修改一段连续区间的值 
 以给区间[a,b]的每个数都加x为例讲解 
 思路 
 修改只对我们有用的区间，其他的没用到的我们就不用修改
 
void change_interval(int rt)//区间修改
{
    if(tree[rt].l >= a && tree[rt].r <=b)
    {
        tree[rt].w += (tree[rt].r - tree[rt].l + 1) * s;
        tree[rt].mark += s;
        return;
    }
    if(tree[rt].mark)   down(rt);
    int m = (tree[rt].l + tree[rt].r)/2;
    if(a <= m)  change_interval(rt<<1);
    if(b > m)   change_interval(rt<<1|1);
    tree[rt].w = tree[rt<<1].w + tree[rt<<1|1].w;
}
 
8.总结
 
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
const int N = 1000 + 10;
//用位运算速度快
int x, y, ans, s, a, b;

struct node
{
    int l, r, w, mark;//记录左孩子，右孩子，区间和，还有延时标记
}tree[N*4];

void build(int l, int r, int rt)//l,r表示当前节点区间，rt表示当前节点编号
{
    tree[rt].l = l; tree[rt].r = r;
    if(l == r){//说明到达叶子节点
        scanf("%d", &tree[rt].w);
        return;
    }
    int m = (l+r)/2;//二分
    build(ls);//建立左子树
    build(rs);//建立右子
    tree[rt].w = tree[rt<<1].w + tree[rt<<1|1].w;//状态合并，此结点的w=两个孩子的w之和
}

void down(int rt)//标记下传
{
    tree[rt<<1].mark += tree[rt].mark;
    tree[rt<<1|1].mark += tree[rt].mark;
    tree[rt<<1].w += tree[rt].mark*(tree[rt<<1].r-tree[rt<<1].l+1);
    tree[rt<<1|1].w += tree[rt].mark*(tree[rt<<2|1].r-tree[rt<<2+1].l+1);
    tree[rt].mark = 0;
}

void ask_poi(int rt)//rt表示当前节点编号 单点查询
{
    if(tree[rt].l == tree[rt].r)//当该结点的左右端点相等，是叶子节点，是最终答案
    {
        ans = tree[rt].w;
        return;
    }
    if(tree[rt].mark)   down(rt);//懒标志下传
    int m = (tree[rt].l + tree[rt].r)/2;
    if(x <= m)
        ask_poi(rt<<1);//目标位置比中点靠左,就递归左孩子
    else
        ask_poi(rt<<1|1);//反之,递归右孩子
}

void change_poi(int rt)//rt表示当前节点编号 单点修改
{
    if(tree[rt].l == tree[rt].r)//找到目标位置
    {
        tree[rt].w += s;
        return;
    }
    if(tree[rt].mark)   down(rt);
    int m = (tree[rt].l + tree[rt].r)/2;
    if(x<=m)    change_poi(rt<<1);
    else    change_poi(rt<<1|1);
    tree[rt].w = tree[rt<<1].w + tree[rt<<1|1].w;
}

void ask_interval(int rt)//区间查询
{
    if(tree[rt].l >= a && tree[rt].r <=b)
    {
        ans += tree[rt].w;
        return;
    }
    if(tree[rt].mark)   down(rt);
    int m = (tree[rt].l + tree[rt].r)/2;
    if(a <= m)  ask_interval(rt<<1);
    if(b > m)   ask_interval(rt<<1|1);
}

void change_interval(int rt)//区间修改
{
    if(tree[rt].l >= a && tree[rt].r <=b)
    {
        tree[rt].w += (tree[rt].r - tree[rt].l + 1) * s;
        tree[rt].mark += s;
        return;
    }
    if(tree[rt].mark)   down(rt);
    int m = (tree[rt].l + tree[rt].r)/2;
    if(a <= m)  change_interval(rt<<1);
    if(b > m)   change_interval(rt<<1|1);
    tree[rt].w = tree[rt<<1].w + tree[rt<<1|1].w;
}
 
三.空间优化
 
父节点为k，左孩子2k，右孩子2k+1 
 所以平常的线段树节点下标数处于【2N，4N】之间，但我们空间每次都要开到4N，所以这经常会出现空间浪费的问题。那怎么办呢~ 
 这里我们可以用到100%空间利用率的 dfs遍历次序当做下标的编号方式
 
转载自：http://www.cppblog.com/MatoNo1/archive/2015/05/05/195857.html 
 跨度为6的线段树： 
  
 容易发现，根结点下标为1，下标为A的结点的左子结点下标为(A+1)，右子结点下标为A+SZ(A.L)+1，其中SZ(A.L)为A的左子树大小。 
 若A的左右端点为l、r，mid=(l+r)/2（下取整），则A的左子树所表示的线段为[l, mid]，所以SZ(A.L)=(mid-l+1)*2-1=(mid-l)*2+1=((r-l-1)/2（上取整）)*2+1 
 这样，A的右子结点下标就是A+((r-l+1)/2（上取整))*2，也就是A加上大于(r-l)的最小的偶数； 
 写在代码里就是： 
 
写在代码里就是：
int mid=l+r>>1;
opr(l, mid, A+1);
opr(mid+1, r, (r-l&1?A+r-l+1:A+r-l+2));
 
或者，借助位运算，可以免去条件判断： 
 
int mid=l+r>>1;
opr(l, mid, A+1);
opr(mid+1, r, A+r-l+2-((r^l)&1));
 
经测试，后者（使用位运算的）虽然总的运算次数多于前者（使用条件判断的），但后者比前者快一点点，其原因可能与C语言中的条件运算符速度较慢有关；
 
这样，我们就成功地将线段树下标的空间利用率提高到了100%！！以后只需要开2N空间就行了囧…… 
 与传统表示法相比，这种新式表示法虽然可以节省空间，但时间消耗要更大一些（时间和空间总是矛盾的囧……），因为它在找右子结点的时候需要较多的运算。平均起来，新式表示法比传统表示法要慢10~15%，对于某些坑爹的数据（对右子结点调用比较多的那种）可能慢得更多。此外，在下放标记的时候，传统表示法只需要知道结点下标就行了，而新式表示法必须同时知道结点的左右端点，这样在dm中就需要传递三个参数，从而要慢一些，当然，我们可以不用dm，直接在操作里面写标记下放。
 
四.zkw线段树
 
转载自：http://blog.csdn.net/qq_18455665/article/details/50989113
 
前言
 
首先说说出处：
清华大学 张昆玮(zkw) - ppt 《统计的力量》
本文(辣鸡)编辑：BeiYu
写这篇博客的原因： 
1.zkw线段树非递归，效率高，代码短 
2.网上关于zkw线段树的讲解实在是太少了 
3.个人感觉很实用
 
更新日志
 
20160327-Part 1(zkw线段树的建立)
20160329-Part 2(单点操作)
20160329-Part 3(区间操作)
 
Part 1
 
来说说它的构造
 
线段树的堆式储存
 
 
我们来转成二进制看看
 
 
小学生问题:找规律
 
规律是很显然的
 
一个节点的父节点是这个数左移1，这个位运算就是低位舍弃，所有数字左移一位
一个节点的子节点是这个数右移1，是左节点，右移1+1是右节点
同一层的节点是依次递增的，第n层有2^(n-1)个节点
最后一层有多少节点，值域就是多少(这个很重要)
 
有了这些规律就可以开始着手建树了
 
查询区间[1,n]
 
最后一层不是2的次幂怎么办? 
 开到2的次幂！后面的空间我不要了！就是这么任性！ 
 Build函数就这么出来了！找到不小于n的2的次幂 
 直接输入叶节点的信息
 
int n,M,q;int d[N<<1];
inline void Build(int n){
    for(M=1;M<n;M<<=1);
    for(int i=M+1;i<=M+n;i++) d[i]=in();
}
 
建完了？当然没有！父节点还都是空的呢！ 
 
维护父节点信息？ 
 
倒叙访问，每个节点访问的时候它的子节点已经处理过辣！
 
维护区间和？
 
for(int i=M-1;i;--i) d[i]=d[i<<1]+d[i<<1|1];
 
维护最大值？
 
for(int i=M-1;i;--i) d[i]=max(d[i<<1],d[i<<1|1]);
 
维护最小值？
 
for(int i=M-1;i;--i) d[i]=min(d[i<<1],d[i<<1|1]);
 
这样就构造出了一颗二叉树，也就是zkw线段树了！ 
 
如果你是压行选手的话(比如我)，建树的代码只需要两行。 
 是不是特别Easy! 
 新技能Get√
 
Part 2
 
单点操作
 
单点修改

void Change(int x,int v){
    d[M+x]+=v;
}
 
只是这么简单？当然不是，跟线段树一样，我们要更新它的父节点！
 
void Change(int x,int v){
    d[x=M+x]+=v;
    while(x) d[x>>=1]=d[x<<1]+d[x<<1|1];
}
 
没了？没了。
 
单点查询(差分思想，后面会用到)
 
把d维护的值修改一下，变成维护它与父节点的差值(为后面的RMQ问题做准备) 
 建树的过程就要修改一下咯！
 
void Build(int n){
    for(M=1;M<=n+1;M<<=1);for(int i=M+1;i<=M+n;i++) d[i]=in();
    for(int i=M-1;i;--i) d[i]=min(d[i<<1],d[i<<1|1]),d[i<<1]-=d[i],d[i<<1|1]-=d[i];
}
 
在当前情况下的查询
 
void Sum(int x,int res=0){
    while(x) res+=d[x],x>>=1;return res;
}
 
Part 3 
 
区间操作
 
询问区间和，把[s,t]闭区间换成(s,t)开区间来计算
 
    int Sum(int s,int t,int Ans=0){
        for (s=s+M-1,t=t+M+1;s^t^1;s>>=1,t>>=1){
            if(~s&1) Ans+=d[s^1];
            if( t&1) Ans+=d[t^1];
        }return Ans;
    }
 
为什么~s&1?
 
为什么t&1? 
  
 变成开区间了以后，如果s是左儿子，那么它的兄弟节点一定在区间内，同理，如果t是右儿子，那么它的兄弟节点也一定在区间内！
 
这样计算不会重复吗？
 
答案是会的！所以注意迭代的出口s^t^1 
 如果s,t就是兄弟节点，那么也就迭代完成了。
 
代码简单，即使背过也不难QuQ
 
区间最小值
 
void Sum(int s,int t,int L=0,int R=0){
    for(s=s+M-1,t=t+M+1;s^t^1;s>>=1,t>>=1){
        L+=d[s],R+=d[t];
        if(~s&1) L=min(L,d[s^1]);
        if(t&1) R=min(R,d[t^1]);
    }
    int res=min(L,R);while(s) res+=d[s>>=1];
}
 
差分！ 
 
不要忘记最后的统计！ 
 还有就是建树的时候是用的最大值还是最小值，这个一定要注意，影响到差分。
 
区间最大值
 
   void Sum(int s,int t,int L=0,int R=0){
        for(s=s+M-1,t=t+M+1;s^t^1;s>>=1,t>>=1){
            L+=d[s],R+=d[t];
            if(~s&1) L=max(L,d[s^1]);
            if(t&1) R=max(R,d[t^1]);
        }
        int res=max(L,R);while(s) res+=d[s>>=1];
    }
 
同理。
 
区间加法
 
 void Add(int s,int t,int v,int A=0){
        for(s=s+M-1,t=t+M+1;s^t^1;s>>=1,t>>=1){
            if(~s&1) d[s^1]+=v;if(t&1) d[t^1]+=v;
            A=min(d[s],d[s^1]);d[s]-=A,d[s^1]-=A,d[s>>1]+=A;
            A=min(d[t],d[t^1]);d[t]-=A,d[t^1]-=A,d[t>>1]+=A;
        }
        while(s) A=min(d[s],d[s^1]),d[s]-=A,d[s^1]-=A,d[s>>=1]+=A;
    }
 
同样是差分！差分就是厉害QuQ
 
zkw线段树小试牛刀（code来自hzwer.com）
 
  #include<cstdio>
    #include<iostream>
    #define M 261244
    using namespace std;
    int tr[524289];
    void query(int s,int t)
    {
        int ans=0;
        for(s=s+M-1,t=t+M+1;s^t^1;s>>=1,t>>=1)
        {
             if(~s&1)ans+=tr[s^1];
             if(t&1)ans+=tr[t^1];
             }
        printf("%d\n",ans);
    } 
    void change(int x,int y)
    {
        for(tr[x+=M]+=y,x>>=1;x;x>>=1)
           tr[x]=tr[x<<1]+tr[x<<1|1];
    }
    int main()
    {
        int n,m,f,x,y;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){scanf("%d",&x);change(i,x);}
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
        {
                scanf("%d%d%d",&f,&x,&y);
                if(f==1)change(x,y);
                else query(x,y);
                }
        return 0;
    }
 
poj3468（code来自网络）
 
  #include <cstdio>
    #include <cstring>
    #include <cctype>
    #define N ((131072 << 1) + 10) //表示节点个数->不小于区间长度+2的最小2的正整数次幂*2+10
    typedef long long LL;
    inline int getc() {
        static const int L = 1 << 15;
        static char buf[L] , *S = buf , *T = buf;
        if (S == T) {
            T = (S = buf) + fread(buf , 1 , L , stdin);
            if (S == T)
                return EOF;
        }
        return *S++;
    }
    inline int getint() {
        static char c;
        while(!isdigit(c = getc()) && c != '-');
        bool sign = (c == '-');
        int tmp = sign ? 0 : c - '0';
        while(isdigit(c = getc()))
            tmp = (tmp << 1) + (tmp << 3) + c - '0';
        return sign ? -tmp : tmp;
    }
    inline char getch() {
        char c;
        while((c = getc()) != 'Q' && c != 'C');
        return c;
    }
    int M; //底层的节点数
    int dl[N] , dr[N]; //节点的左右端点
    LL sum[N]; //节点的区间和
    LL add[N]; //节点的区间加上一个数的标记
    #define l(x) (x<<1) //x的左儿子，利用堆的性质
    #define r(x) ((x<<1)|1) //x的右儿子，利用堆的性质
    void pushdown(int x) { //下传标记
     if (add[x]&&x<M) {//如果是叶子节点，显然不用下传标记（别忘了）
         add[l(x)] += add[x];
            sum[l(x)] += add[x] * (dr[l(x)] - dl[l(x)] + 1);
            add[r(x)] += add[x];
            sum[r(x)] += add[x] * (dr[r(x)] - dl[r(x)] + 1);
            add[x] = 0; 
        }
    }
    int stack[20] , top;//栈
    void upd(int x) { //下传x至根节点路径上节点的标记（自上而下，用栈实现）
     top = 0;
        int tmp = x;
        for(; tmp ; tmp >>= 1)
            stack[++top] = tmp;
        while(top--)
            pushdown(stack[top]);
    }
    LL query(int tl , int tr) { //求和
     LL res=0;
        int insl = 0, insr = 0; //两侧第一个有用节点
     for(tl=tl+M-1,tr=tr+M+1;tl^tr^1;tl>>=1,tr>>=1) {
            if (~tl&1) {
                if (!insl)
            upd(insl=tl^1);
                res+=sum[tl^1];
            }
            if (tr&1) {
                if(!insr)
            upd(insr=tl^1)
                res+=sum[tr^1];
            }
        }
        return res;
    }
    void modify(int tl , int tr , int val) { //修改
     int insl = 0, insr = 0;
        for(tl=tl+M-1,tr=tr+M+1;tl^tr^1;tl>>=1,tr>>=1) {
            if (~tl&1) {
                if (!insl)
                    upd(insl=tl^1);
                add[tl^1]+=val;
                sum[tl^1]+=(LL)val*(dr[tl^1]-dl[tl^1]+1);
            }
            if (tr&1) {
                if (!insr)
                    upd(insr=tr^1);
                add[tr^1]+=val;
                sum[tr^1]+=(LL)val*(dr[tr^1]-dl[tr^1]+1);
            }
        }
        for(insl=insl>>1;insl;insl>>=1) //一路update
         sum[insl]=sum[l(insl)]+sum[r(insl)];
        for(insr=insr>>1;insr;insr>>=1)
            sum[insr]=sum[l(insr)]+sum[r(insr)];


    }
    inline void swap(int &a , int &b) {
        int tmp = a;
        a = b;
        b = tmp;
    }
    int main() {
        //freopen("tt.in" , "r" , stdin);
     int n , ask;
        n = getint();
        ask = getint();
        int i;
        for(M = 1 ; M < (n + 2) ; M <<= 1);
        for(i = 1 ; i <= n ; ++i)
            sum[M + i] = getint() , dl[M + i] = dr[M + i] = i; //建树
     for(i = M - 1; i >= 1 ; --i) { //预处理节点左右端点
         sum[i] = sum[l(i)] + sum[r(i)];
            dl[i] = dl[l(i)];
            dr[i] = dr[r(i)];
        }
        char s;
        int a , b , x;
        while(ask--) {
            s = getch();
            if (s == 'Q') {
                a = getint();
                b = getint();
                if (a > b)
                    swap(a , b);
                printf("%lld\n" , query(a , b));
            }
            else {
                a = getint();
                b = getint();
                x = getint();
                if (a > b)
                    swap(a , b);
                modify(a , b , x);
            }
        }
        return 0;
    }
 
可持久化线段树版本？！（来自http://blog.csdn.net/forget311300/article/details/44306265）
 
  #include <iostream>  
    #include <cstdio>  
    #include <cstring>  
    #include <cmath>  
    #include <algorithm>  
    #include <vector>  
    #define mp(x,y) make_pair(x,y)  

    using namespace std;  

    const int N = 100000;  
    const int inf = 0x3f3f3f3f;  

    int a[N + 10];  
    int b[N + 10];  
    int M;  
    int lq, rq;  
    vector<pair<int, int> > s[N * 22];  

    void add(int id, int cur)  
    {  
        cur += M;  
        int lat = 0;  
        if (s[cur].size())  
            lat = s[cur][s[cur].size() - 1].second;  
        s[cur].push_back(mp(id, ++lat));  
        for (cur >>= 1; cur; cur >>= 1)  
        {  
            int l = 0;  
            if (s[cur << 1].size())  
                l = s[cur << 1][s[cur << 1].size() - 1].second;  
            int r = 0;  
            if (s[cur << 1 | 1].size())  
                r = s[cur << 1 | 1][s[cur << 1 | 1].size() - 1].second;  
            s[cur].push_back(mp(id, l + r));  
        }  
    }  

    int Q(int id, int k)  
    {  
        if (id >= M) return id - M;  
        int l = id << 1, r = l ^ 1;  
        int ll = lower_bound(s[l].begin(), s[l].end(), mp(lq, inf)) - s[l].begin() - 1;  
        int rr = lower_bound(s[l].begin(), s[l].end(), mp(rq, inf)) - s[l].begin() - 1;  
        int kk = 0;  
        if (rr >= 0)kk = s[l][rr].second;  
        if (ll >= 0)kk = s[l][rr].second - s[l][ll].second;  
        if (kk < k)return Q(r, k - kk);  
        return Q(l, k);  
    }  

    int main()  
    {  
        int n, m;  
        while (~scanf("%d%d", &n, &m))  
        {  
            for (int i = 0; i < n; i++)  
            {  
                scanf("%d", a + i);  
                b[i] = a[i];  
            }  
            sort(b, b + n);  
            int nn = unique(b, b + n) - b;  
            for (M = 1; M < nn; M <<= 1);  
            for (int i = 1; i < M + M; i++)  
            {  
                s[i].clear();  
                //s[i].push_back(mp(0, 0));  
            }  
            for (int i = 0; i < n; i++)  
            {  
                int id = lower_bound(b, b + nn, a[i]) - b;  
                add(i + 1, id);  
            }  
            while (m--)  
            {  
                int k;  
                scanf("%d %d %d", &lq, &rq, &k);  
                lq--;  
                int x = Q(1, k);  
                printf("%d\n", b[x]);  
            }  
        }  
        return 0;  
    }  
 
完全模板？！（来自http://blog.csdn.net/forget311300/article/details/44306265）
 
const int N = 1e5;  

struct node  
{  
    int sum, d, v;  
    int l, r;  
    void init()  
    {  
        d = 0;  
        v = -1;  
    }  
    void cb(node ls, node rs)  
    {  
        sum = ls.sum + rs.sum;  
        l = ls.l, r = rs.r;  
    }  
    int len()  
    {  
        return r - l + 1;  
    }  
    void V(int x)  
    {  
        sum = len() * x;  
        d = 0;  
        v = x;  
    }  
    void D(int x)  
    {  
        sum += len() * x;  
        d += x;  
    }  
};  

struct tree  
{  
    int m, h;  
    node g[N << 2];  
    void init(int n)  
    {  
        for (m = h = 1; m < n + 2; m <<= 1, h++);  
        int i = 0;  
        for (; i <= m; i++)  
        {  
            g[i].init();  
            g[i].sum = 0;  
        }  
        for (; i <= m + n; i++)  
        {  
            g[i].init();  
            scanf("%d", &g[i].sum);  
            g[i].l = g[i].r = i - m;  
        }  
        for (; i < m + m; i++)  
        {  
            g[i].init();  
            g[i].sum = 0;  
            g[i].l = g[i].r = i - m;  
        }  
        for (i = m - 1; i > 0; i--)  
            g[i].cb(g[i << 1], g[i << 1 | 1]);  
    }  
    void dn(int x)  
    {  
        for (int i = h - 1; i > 0; i--)  
        {  
            int f = x >> i;  
            if (g[f].v != -1)  
            {  
                g[f << 1].V(g[f].v);  
                g[f << 1 | 1].V(g[f].v);  
            }  
            if (g[f].d)  
            {  
                g[f << 1].D(g[f].d);  
                g[f << 1 | 1].D(g[f].d);  
            }  
            g[f].v = -1;  
            g[f].d = 0;  
        }  
    }  
    void up(int x)  
    {  
        for (x >>= 1; x; x >>= 1)  
        {  
            if (g[x].v != -1)continue;  
            int d = g[x].d;  
            g[x].d = 0;  
            g[x].cb(g[x << 1], g[x << 1 | 1]);  
            g[x].D(d);  
        }  
    }  
    void update(int l, int r, int x, int o)  
    {  
        l += m - 1, r += m + 1;  
        dn(l), dn(r);  
        for (int s = l, t = r; s ^ t ^ 1; s >>= 1, t >>= 1)  
        {  
            if (~s & 1)  
            {  
                if (o)  
                    g[s ^ 1].V(x);  
                else  
                    g[s ^ 1].D(x);  
            }  
            if (t & 1)  
            {  
                if (o)  
                    g[t ^ 1].V(x);  
                else  
                    g[t ^ 1].D(x);  
            }  
        }  
        up(l), up(r);  
    }  
    int Q(int l, int r)  
    {  
        int ans = 0;  
        l += m - 1, r += m + 1;  
        dn(l), dn(r);  
        for (int s = l, t = r; s ^ t ^ 1; s >>= 1, t >>= 1)  
        {  
            if (~s & 1)ans += g[s ^ 1].sum;  
            if (t & 1)ans += g[t ^ 1].sum;  
        }  
        return ans;  
    }  
};  
 
二维情况（来自http://blog.csdn.net/forget311300/article/details/44306265）
 
  #include <cstdio>  
    #include <algorithm>  
    #include <cstring>  
    #include <cmath>  
    #include <vector>  
    #include <iostream>  

    using namespace std;  

    const int W = 1000;  

    int m;  

    struct tree  
    {  
        int d[W << 2];  
        void o()  
        {  
            for (int i = 1; i < m + m; i++)d[i] = 0;  
        }  
        void Xor(int l, int r)  
        {  
            l += m - 1, r += m + 1;  
            for (int s = l, t = r; s ^ t ^ 1; s >>= 1, t >>= 1)  
            {  
                if (~s & 1)d[s ^ 1] ^= 1;  
                if (t & 1)d[t ^ 1] ^= 1;  
            }  
        }  

    } g[W << 2];  

    void chu()  
    {  
        for (int i = 1; i < m + m; i++)  
            g[i].o();  
    }  


    void Xor(int lx, int ly, int rx, int ry)  
    {  
        lx += m - 1, rx += m + 1;  
        for (int s = lx, t = rx; s ^ t ^ 1; s >>= 1, t >>= 1)  
        {  
            if (~s & 1)g[s ^ 1].Xor(ly, ry);  
            if (t & 1)g[t ^ 1].Xor(ly, ry);  
        }  
    }  

    int Q(int x, int y)  
    {  
        int ans = 0;  
        for (int xx = x + m; xx; xx >>= 1)  
        {  
            for (int yy = y + m; yy; yy >>= 1)  
            {  
                ans ^= g[xx].d[yy];  
            }  
        }  
        return ans;  
    }  

    int main()  
    {  
        int T;  
        cin >> T;  
        int fl = 0;  
        while (T--)  
        {  
            if (fl)  
            {  
                printf("\n");  
            }  
            fl = 1;  
            int N, M;  
            cin >> N >> M;  
            for (m =  1; m < N + 2; m <<= 1);  
            chu();  
            while (M--)  
            {  
                char o[4];  
                scanf("%s", o);  
                if (*o == 'Q')  
                {  
                    int x, y;  
                    scanf("%d%d", &x, &y);  
                    printf("%d\n", Q(x, y));  
                }  
                else  
                {  
                    int lx, ly, rx, ry;  
                    scanf("%d%d%d%d", &lx, &ly, &rx, &ry);  
                    Xor(lx, ly, rx, ry);  
                }  
            }  
        }  
        return 0;  
    }  
 
非递归扫描线+离散化？！（来自http://blog.csdn.net/forget311300/article/details/44306265）
 
   #include <algorithm>  
    #include <iostream>  
    #include <cstdio>  
    #include <cstring>  
    #include <vector>  
    #include <cmath>  

    using namespace std;  

    const int N = 111;  

    int n;  
    vector<double> y;  

    struct node  
    {  
        double s;  
        int c;  
        int l, r;  
        void chu(double ss, int cc, int ll, int rr)  
        {  
            s =  ss;  
            c = cc;  
            l = ll, r = rr;  
        }  
        double len()  
        {  
            return y[r] - y[l - 1];  
        }  
    } g[N << 4];  
    int M;  

    void init(int n)  
    {  
        for (M = 1; M < n + 2; M <<= 1);  
        g[M].chu(0, 0, 1, 1);  
        for (int i = 1; i <= n; i++)  
            g[i + M].chu(0, 0, i, i);  
        for (int i = n + 1; i < M; i++)  
            g[i + M].chu(0, 0, n, n);  
        for (int i = M - 1; i > 0; i--)  
            g[i].chu(0, 0, g[i << 1].l, g[i << 1 | 1].r);  
    }  

    struct line  
    {  
        double x, yl, yr;  
        int d;  
        line() {}  
        line(double x, double yl, double yr, int dd): x(x), yl(yl), yr(yr), d(dd) {}  
        bool operator < (const line &cc)const  
        {  
            return x < cc.x || (x == cc.x && d > cc.d);  
        }  
    };  

    vector<line>L;  

    void one(int x)  
    {  
        if (x >= M)  
        {  
            g[x].s = g[x].c ? g[x].len() : 0;  
            return;  
        }  
        g[x].s = g[x].c ? g[x].len() : g[x << 1].s + g[x << 1 | 1].s;  
    }  

    void up(int x)  
    {  
        for (; x; x >>= 1)  
            one(x);  
    }  

    void add(int l, int r, int d)  
    {  
        if (l > r)return;  
        l += M - 1, r += M + 1;  
        for (int s = l, t = r; s ^ t ^ 1; s >>= 1, t >>= 1)  
        {  
            if (~s & 1)  
            {  
                g[s ^ 1].c += d;  
                one(s ^ 1);  
            }  
            if (t & 1)  
            {  
                g[t ^ 1].c += d;  
                one(t ^ 1);  
            }  
        }  
        up(l);  
        up(r);  
    }  

    double sol()  
    {  
        y.clear();  
        L.clear();  
        for (int i = 0; i < n; i++)  
        {  
            double lx, ly, rx, ry;  
            scanf("%lf %lf %lf %lf", &lx, &ly, &rx, &ry);  
            L.push_back(line(lx, ly, ry, 1));  
            L.push_back(line(rx, ly, ry, -1));  
            y.push_back(ly);  
            y.push_back(ry);  
        }  
        sort(y.begin(), y.end());  
        y.erase(unique(y.begin(), y.end()), y.end());  
        init(y.size());  
        sort(L.begin(), L.end());  
        n = L.size() - 1;  
        double ans = 0;  
        for (int i = 0; i < n; i++)  
        {  
            int l = upper_bound(y.begin(), y.end(), L[i].yl + 1e-8) - y.begin();  
            int r = upper_bound(y.begin(), y.end(), L[i].yr + 1e-8) - y.begin() - 1;  
            add(l, r, L[i].d);  
            ans += g[1].s * (L[i + 1].x - L[i].x);  
        }  
        return ans;  
    }  

    int main()  
    {  
        int ca = 1;  
        while (cin >> n && n)  
        {  
            printf("Test case #%d\nTotal explored area: %.2f\n\n", ca++, sol());  
        }  
        return 0;  
    }