之所以叫v1.0呢，是因为这是我第一次学这个数据结构。
考虑到重要性，以后在做题的过程中会对这篇博客做更新的。
线段树是一种二叉搜索树，用于处理区间问题的数据结构。
与ST表不同的是，线段树支持点，区间修改。相应的，虽然预处理速度与ST表相同，都是\(O(logn)\)，但查询速度比起ST表的\(O(1)\)要慢，是\(O(logn)\)。
线段树是建立在区间二分这个概念上的，树上的每个节点都代表了一段区间。
如图
对于二叉树这种结构，一般都用的是递归的方式。用指针难免会比较难处理，所以可以用完全二叉树的数组储存的方式，将线段树存放到数组里。
对于上图的线段树，用数组储存后的表现是
这样储存，大概率会需要比较多的空间。一般来说，有n个点时需要4n的空间（\(2\times 2^k(2^{k-1}<n<2^k)\)）
如果学过完全二叉树，那么父子节点的关系就很清楚。设父节点下标为K，则有
因为父子节点的关系有2倍关系，经常会用位运算的方式来计算下标，如
既然是一种二叉树的结构，一般用递归来做会比较简单。
const int maxn = 1e2 + 10;
int a[maxn] = {0, 1, 2, 3, 4, 5, 6, 7};//原数组
int tree[maxn * 4];//需要建树的
void print(int n)//输出tree的函数，这个自己随便写写，方便看就行
{
for (int i = 1; i < n * 4; i++)
{
if ((i & (i - 1)) == 0)
cout << endl;
cout << setw(4) << tree[i];
}
}
void Pushup(int k)//更新函数 k:线段树节点下标
{
tree[k] = max(tree[k * 2], tree[k * 2 + 1]);//这里以最大值为例，这句话视题目意思而定
}
void Build(int l, int r, int k)//建树函数 l:原数组a的左端点 r:原数组a的右端点 k:当前线段树节点下标
{
//比如该例中a要建树的范围是1~7，那么l=1,r=7
//k默认选1.不要选0！0*2=0，失去了找子节点的功能
//一开始建树的时候，k指的就是根节点所在下标
if (l == r)//左右端点相等，说明现在是一个点，直接把原数组的东西复制过来
tree[k] = a[l];
else//否则就肯定是一段区间
{
int m = (l + r) / 2;//确定中点
Build(l, m, k * 2);//递归建左子树
Build(m + 1, r, k * 2 + 1);//递归建右子树
//这两句位置变动没有影响，不过要注意范围和k的值
Pushup(k);//更新当前节点
}
}
int main()
{
Build(1, 7, 1);//a数组下标1~7的建树，tree数组从1开始
print(7);
return 0;
}
结果如图：
PS：7下面是空的
点更新很易于理解。从需要更改的根节点出发，将每一个覆盖到这个点的区间都更新一次即可。
void updata(int p,int val,int l,int r,int k)//p:需要更改的原数组下标 val:增加的值 l:原数组的左端点 r:原数组的右端点 k:
{
if (l==r)//说明是单点，加上就好了
a[p] += val, tree[k] += val;//原数组和线段树数组都加
else{
int m = (l + r) / 2;//中点
if (p<=m){//要修改的点在左子树上，记得有等于号！
updata(p, val, l, m, k * 2);
}else{//在右子树上
updata(p, val, m + 1, r, k * 2 + 1);
}
Pushup(k);//更新当前节点
}
}
也很容易理解：查询的是一段区间，我们只需要将这个区间所包含的子区间——也就是在预处理中已经算好的值都拿出来就行
代码如下：
int Query(int L, int R, int l, int r, int k)//L,R:要查询的区间范围 l,r:当前的区间范围 k:当前线段树下标
{
if (L <= l && r <= R)//当前区间完全包含在查询区间内，直接返回
return tree[k];
else
{
//可能包括了左端点，也可能有右端点
int res = 0;//答案，注意初始化的值要随题目意思改变
int m = (l + r) / 2;//中点
if (L <= m)//左子树与查询区间有交集
res = max(res, Query(L, R, l, m, k * 2));//这句话应题目意思而变，该例中是最大值
if (R >= m+1)//右子树与查询区间有交集，注意右区间从m+1开始
res = max(res, Query(L, R, m + 1, r, k * 2 + 1));
return res;//返回答案
}
}
其实查询比上面两种操作还是要难，配合图片更容易理解
这里假设要查询2~5之间的最大值
原文：https://www.cnblogs.com/Salty-Fish/p/13261524.html