线段树学习笔记
对线段树的介绍
- 线段树是一种树形数据结构，属于二叉树
- 一棵线段树的每个结点都可以用区间\([l,r]\)来表示。线段树的叶结点表示的区间为\([l,l]\)或\([r,r]\)。
- 线段树支持单点修改，区间修改，区间和/区间最值等的查询。
- 对于线段树的区间修改一般采用延迟修改方式
- 线段树去掉最后一层后是一棵满二叉树
线段树的建树
线段树的表示
因为线段树是一棵二叉树，所以可以采用与二叉堆一致的表示法：
编号为p的结点的
- 左结点的编号为\(p\times2\)
- 右结点的编号为\(p\times2+1\)
类似二叉堆，线段树是一个结构体数组。
C++ - 6 行
struct SegmentTree
{
int l,r;// 表示该结点代表的区间
int dat;//区间[l,r]的最大值
int add;//延迟修改标记
}
线段树的结点
为了避免最最让人难受的RE，所以考虑一棵线段树的最大结点数。
设现在需要表示区间\([1,n]\)，使得构造的线段树为一棵满二叉树。
由线段树的性质得知，该二叉树有\(n\)个叶结点，则总结点数为\(n+n\div2+n\div4+···+2+1\)，即\(4n-1\)。
因为我的个人习惯，我一般会不处理一个数组的第一个元素，即下标为\(0\)的元素。
C++ - 27 行
#include<bits/stdc++.h>
using namespace std;
struct SegmentTree
{
int l,r;// 表示该结点代表的区间
int dat;//区间[l,r]的最大值
int add;//延迟修改标记
} t[4*1000001];
int va[114514];//区间是数组下标区间，这是线段树叶结点实际代表的值
void bulid(int l,int r,int p)// 结点的数组下标为p，表示区间[l,r]
{
t[p].l = l;//代表区间初始化
t[p].r = r;
if(l == r)//叶结点
{
t[p].dat = va[l];
return;// 如果你想RE，建议删去这行
}
int mid = (l + r) / 2;
bulid(l,mid,p*2);// 左子结点
bulid(mid+1,r,p*2+1);//右子结点
t[p].dat = max(t[p*2].dat,t[p*2+1].dat);//自下往上更新数据
}
int main()
{
//略
}