🔧 线段树的构建与操作

📦 信息与更新结构

• Info 结构体：每个节点维护区间的信息，比如区间和、最大值、最小值等；支持合并（ operator+ ）和更新（ apply ）。
• Laz 结构体：用于记录对某一段区间的修改请求。它可作用于 Info 的懒更新。

struct Laz 
{
    int add = 0;
    void apply(const Laz &tag) 
    { 
        if (tag.add)
            add += tag.add; 
    }
};

template <typename T>
struct Info 
{
    int sum = 0, mx = 0, mn = 0;
    Info() {}
    Info(T x) : sum(x), mx(x), mn(x) {}
    void apply(const Laz &tag, int len) 
    {
        if (tag.add) 
        {
            mn += tag.add;
            mx += tag.add;
            sum += tag.add * len;
        }
    }

    Info operator+(const Info &a) const 
    {
        Info res;
        res.mn = min(mn, a.mn);
        res.mx = max(mx, a.mx);
        res.sum = sum + a.sum;
        return res;
    }
};

🧱 构建线段树

线段树的构建通常采用递归的方式，设当前节点为 u ，若其管辖区间的长度已为 1 ，则可根据所需初始化该节点。 否则将该区间对半划分为两个子区间，分别进入左右子节点递归建树，最后合并两个子节点的信息（ push_up ）。

void build(int l, int r, int u)
{
    // 对 [l, r] 区间简历线段树，当前根的编号为 u
    if (l == r)
    {
        info[u] = Info(arr[l]);
        return;
    }

    int mid = (l + r) >> 1;
    // 递归对左右区间建树
    build(l, mid, u << 1);
    build(mid + 1, r, u << 1 | 1);
    // 合并左右子节点的信息
    push_up(u);
}

🎯 构建过程可视化

⚙️ 信息维护：push_up 与 push_down

• push_up ：用于更新当前节点的信息。它的作用是将左右子节点的信息通过区间合并（ operator+ ）向上传递， 更新当前节点的统计数据（如区间和、最小值、最大值等）。这个过程确保了每次修改或查询操作后，整棵线段树的状态始终是最新的。
• push_down ：用于懒标记（ lazy tag ）的传递。当一个节点上存在尚未向下传播的更新信息时，调用此函数会将该节点的懒标记应用到它的左右子节点，使得这些子节点的数据能够正确反映出应有的更新效果。随后，将当前节点的懒标记清空，避免重复更新。懒标记能减少重复更新操作，提高效率。

void apply(int u, Laz tag, int len) 
{
    laz[u].apply(tag);
    info[u].apply(tag, len);
}

void push_up(int u) { info[u] = info[u << 1] + info[u << 1 | 1]; }

void push_down(int u, int llen, int rlen) 
{
    apply(u << 1, laz[u], llen);
    apply(u << 1 | 1, laz[u], rlen);
    // 清空当前节点的懒标记
    laz[u] = Laz();
}

✏️ 区间修改

线段树的区间修改可以对一个连续子区间统一修改。懒标记允许先记录修改指令，而不立即递归更新所有子节点，从而提升修改效率，直到真正访问子节点时再下传修改。

• 如果当前节点负责的区间 [l, r] 完全被覆盖，直接用 apply 应用懒标记并返回。
• 否则先通过 push_down 把当前节点的懒标记传递给左右子节点，保证子节点信息最新。
• 递归修改左子区间（如果有交集）和右子区间（如果有交集）。
• 最后用 push_up 合并左右子节点的信息，更新当前节点。

void modify(int jobl, int jobr, Laz tag, int l, int r, int u) 
{
    // [jobl, jobr] 为修改区间，[l, r] 为当前节点包含的区间，u 为当前节点编号
    if (jobl <= l && jobr >= r) 
    {
        // 当前区间为查询区间的子集时直接修改当前节点的值，然后打标记，结束修改
        apply(u, tag, r - l + 1);
        return;
    }

    int mid = (l + r) >> 1;
    // 下传懒标记到左右子节点
    push_down(u, mid - l + 1, r - mid);
    // 如果修改区间与左节点区间有交集，则递归修改左子节点
    if (jobl <= mid) modify(jobl, jobr, tag, l, mid, u << 1);
    // 如果修改区间与右节点区间有交集，则递归修改右子节点
    if (jobr > mid) modify(jobl, jobr, tag, mid + 1, r, u << 1 | 1);
    push_up(u);
}

🔧 可视化修改与数据维护

在此处输入新的数组数据（以空格分隔，例如 1 1 4 5 1 4），然后点击更新按钮。线段树将根据新数据重建，并同时计算和显示数组的最大值、最小值与总和。

🔍 区间查询

查询指定区间的合并结果：

Info query(int jobl, int jobr, int l, int r, int u) 
{
    // [jobl, jobr] 为查询区间，[l, r] 为当前节点包含的区间，u 为当前节点编号
    if (jobl <= l && jobr >= r) 
        // 当前区间为查询区间的子集时直接返回当前节点的信息
        return info[u];

    int mid = (l + r) >> 1;
    push_down(u, mid - l + 1, r - mid);
    // 如果查询区间与左右子节点区间均有交集，则递归查询左右子节点，并合并二者信息
    if (jobl <= mid && jobr > mid) 
        return query(jobl, jobr, l, mid, u << 1) + query(jobl, jobr, mid + 1, r, u << 1 | 1);
    // 如果查询区间与左子节点区间有交集，则递归查询左子节点
    else if (jobl <= mid) 
        return query(jobl, jobr, l, mid, u << 1);
    // 如果查询区间与右子节点区间有交集，则递归查询右子节点
    else
        return query(jobl, jobr, mid + 1, r, u << 1 | 1);
}

🔍 可视化查询与数据维护

在此处输入数组数据（以空格分隔，例如 1 1 4 5 1 4），然后点击更新按钮。线段树将根据数据重建，并同时计算和显示数组的最大值、最小值与总和。输入查询区间后，可直接查询或步进查看查询过程。

📌 小贴士

• 建议使用堆式存储法：设节点编号为 u，其左右儿子分别为 2u 与 2u+1。
• 实际应用中空间开辟可使用 4n 作为数组大小上限。

🎯 互动小测

通过以下选择题测试你对线段树的理解程度！

⚙️ 自定义设置