本文共 1961 字，大约阅读时间需要 6 分钟。

线段树的建筑与更新过程就像一座站在_MONITOR_转台上看不见的城市，所有细节都隐藏在代码之下。让我告诉你，这个结构是如何工作的。

首先，线段树的核心是每个节点，它们保存着相关的信息：

• ans：记录当前区间内最长的连续空房数。
• pans：记录从区间左端开始的最长连续空房数。
• sans：记录从区间右端开始的最长连续空房数。

这三个值在每个节点中都有对应的字段，确保在合并子节点时能够准确反映整个父节点的状态。

为了便于解释，我会从组建线段树开始，直到操作更新和查询的过程。

文件结构

包括以下内容：

#include 
   
    using namespace std;#define ll long longconst int maxn = 5e5 + 7;const ll inf = 34359738370;
   

自定义了一个线段树：

struct node {    int ans;    int pans, sans;} tree[maxn << 2];int tag[maxn << 2];int n, m;

辅助函数：

inline int lc(int rt) {    return rt << 1;}inline int rc(int rt) {    return rt << 1 | 1;}inline void pushup(int rt, int l, int r) {    int mid = (l + r) >> 1;    int m = tree[lc(rt)].sans + tree[rc(rt)].pans;    tree[rt].ans = max(max(tree[lc(rt)].ans, tree[rc(rt)].ans), m);}

组建线段树

构建函数：

inline void build(int rt, int l, int r) {    if(l == r) {        tree[rt].ans = 1;        return;    }    int mid = (l + r) >> 1;    build(lc(rt), l, mid);    build(rc(rt), mid+1, r);    pushup(rt, l, r);}

更新操作

更新函数：

inline void updata(int rt, int l, int r, int vl, int vr, int v) {    if(r < vl || l > vr) return;    if(vl <= l && r <= vr) {        if(v == 0) {            tree[rt].ans = tree[rt].pans = tree[rt].sans = 0;            tag[rt] = 1;        } else {            tree[rt].ans = tree[rt].pans = tree[rt].sans = r - l + 1;            tag[rt] = 2;        }        return;    }    pushdown(rt, l, r);    int mid = (l + r) >> 1;    updata(lc(rt), l, mid, vl, vr, v);    updata(rc(rt), mid+1, r, vl, vr, v);    pushup(rt, l, r);}

查询操作

查询函数：

inline int query(int rt, int l, int r, int x) {    pushdown(rt, l, r);    if(l == r) return l;    int mid = (l + r) >> 1;    if(tree[lc(rt)].ans >= x) {        return query(lc(rt), l, mid, x);    }    if(tree[lc(rt)].sans + tree[rc(rt)].pans >= x) {        return mid + 1 - tree[lc(rt)].sans;    }    return query(rc(rt), mid+1, r, x);}

线段树通过递归分割区间，管理各层处理任务。使用时，可以通过更新和查询方法，实现对特定区间的操作。节点标记和分裂功能确保数据在合并和分割时准确传递信息。

理论上，这个线段树可以处理多种区间操作，适用于需要快速、高效处理区间问题的场景。

转载地址：http://ykjyk.baihongyu.com/