数据结构-线段树

概述

线段树可以以极高的效率查询一个区间内动态的数据的总和（没错说的很平淡）。简单的说就是给你一组数据，然后问题是求第i个数据到第j个数据之间所有数据值得总和是多少。当然，这些数据不是一成不变的（这就是线段树和树状数组的区别）。
事实上，在学习了树状数组之后再来学习线段树的效果会更好。事实上它们是连贯的知识，只是被贴上了不同的标签，以至于看起来它们分道扬镳。当然，如果学习完了线段树，有一句忠告不能忘：能用树状数组就不要用线段树，要不然万一跪了吃亏的是自己。

线段树基础

概念

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为$O(logN)$。而未优化的空间复杂度为$2N$，实际应用时一般还要开4N的数组以免越界，因此有时需要离散化让空间压缩。
——著名权威学者 百度词条

我引用了百度词条的这样一句话，似乎有点难懂。我尝试性的解说一下：线段树是建立在线段基础之上的二叉树，并且除了叶子节点以外，其它的节点的值为其左儿子与右儿子的值之和。

解析

我们可以通过构造一棵树（也就是尝试画一棵线段树），来更为直观的感受线段树其中的含义。第一步，线段树是建立在线段上的（可以理解为建立在线性数据上），那么我们就先画一个数组（就是一种常用的线性数据），我们先不管它上面会长成什么模样。

当然了，因为前面提到树状数组是求一个区间内的数据总和，所以我们标记一下每个点代表的区间。因为现在都是叶子节点（它们没有儿子！），所以当前每个点所代表的区间就是它自己到它自己。

接下来，我们会以一种很容易理解的方式，找到这些叶子节点的爸爸。在线段树中，我们可以这样理解：每两个儿子共有一个爸爸（滑稽），并且这个爸爸的值就是两个儿子的值之和，于是就能很轻松的往上推一层。

接下来如上分析，再找爸爸的爸爸。 这边要注意一点，必须是两个儿子才能配对一个爸爸。

接着找爸爸（一脸滑稽）。一般一只找到再也配对不出爸爸的时候算构建完成。

至此，爸爸都找完了，您也就构造好了一棵线段树。 所以我们可以总结一下，构造线段树的构成可以理解为找爸爸（其实应该是创造爸爸，因为本身没有爸爸的）

线段树模板

线段树的模板是很常用的，但是一般不建议魔改（容易写跪）。线段树的模板主要包含三个函数（如果要做到区间修改的话可能需要多些一个），在正常

#if 0
声明
#endif
const MAXN=100100;
int rowData[MAXN]={0};

定义结构体Node

$Segtree$中的每一个节点Node都需要包含：左边界（l:left），右边界（r:rigth）以及这一区间内的总和（data）。

struct Node{
	int l,r;
	long long data;
}segtree[MAXN<<2];

构造函数Build

在使用线段树直线，必须先得构造出线段树的模型。

void Build(int i,int l,int r){
	segtree[i].l=l;
	segtree[i].r=r;
	if(l==r){
		segtree[i].data=rawData[i];
		return;
	}
	int mid=(l+r)>>1;
	Build(i<<1,l,mid);
	Build(i<<1|1,mid+1,r);
	segtree[i].data=segtree[i<<1].data+segtree[i<<1|1].data;
	return;
}

（持续更新中…）（好吧我想颓了）（逃