脚本宝典收集整理的这篇文章主要介绍了线段树,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
build函数: build(u, l, r):u表示当前节点编号,l、r分别是该节点所代表区间的左右端点[l, r].
struct SegmentTree{
int l, r;
int dat;
}t[SIZE * 4];
void build(int u, int L, int R)
{
t[u].l = L, t[u].r = R;
if (L == R) {
t[u].dat = a[L];
return;
}
int mid = (L + R) >> 1;
build(2*u, L, mid);
build(2*u + 1, mid + 1, R);
//一般来说是Pushup()操作;
t[u].dat = max(t[u*2].dat, t[u*2 + 1].dat);
}
线段树中,根节点(编号为1)是执行的入口,需要从根节点出发,递归找到区间[x, x]的叶节点,然后对该节点 进行修改,并自底向上更新信息。@R_498_1304@为O(LOGN):树的高度;
//在节点编号为u,区间x位置处,变更为v;
void change(int u, int x, int v)
{
if (t[u].l == t[u].r) {
t[u].dat = v; return;
}
int mid = (t[u].l + t[u].r) >> 1;
if (x <= mid) {
//左子树遍历;
change(2*u, x, v);
} else {
change(2*u + 1, x , v);
}
//自底向上更新信息;
t[u].dat = max(t[2*u].dat, t[2*u + 1].dat);
}
假设我们所想要查询的区间为[L, R], 线段树所建立的区间为[TL, TR]; 那么从根节点开始,递归执行如下过程:
比如查询区间[l, r]上的最大值;
int Query(int u, int l, int r)
{
if (t[u].l >= l && t[u].r <= r) {
return t[u].dat; //完全包含关系;
}
int mid = (t[u].l + t[u].r) >> 1;
int val = -(1<<30); //-inf;
if (l <= mid) val = max(val, ask(2*u, l, r)); //左子节点有重叠;
if (r > mid) val = max(val, ask(2*u + 1, l, r)); //右子节点有重叠;
return val;
}
以上是脚本宝典为你收集整理的线段树全部内容,希望文章能够帮你解决线段树所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。