..
第六章 线段树
线段树的建立与操作
例1：P3372 【模板】线段树 1
在这里需要注意的是，使用线段树所维护的信息必须具有可合并性。
线段树的应用
例2：P3870 [TJOI2009] 开关
五倍经验
- P2846
- SP7259
- P2574
- P5057
例3：P1438 无聊的数列
考虑等差数列有两个要素：首项 $x$、公差 $y$。只要这两项确定了，等差数列就唯一确定了。
考虑这两个要素也具有 “可加性”：将首项分别为 $x_1$、$x_2$，公差分别为 $y_1$、$y_2$ 的两个等差数列的每一项对应相加，得到的数列也是一个等差数列，且它的首项为 $x_1 + x_2$，公差为 $y_1 + y_2$。
于是使用两个延迟标记，分别表示首相和公差即可。
void Modify(int xNode, int l, int r, long long K, long long D) {
if (l <= node[xNode].l && node[xNode].r <= r) {
node[xNode].tag = true;
node[xNode].K += K + (node[xNode].l - l) * D;
node[xNode].D += D;
return;
}
if (node[xNode].tag) PushDown(xNode);
if (l <= node[node[xNode].lNode].r) Modify(node[xNode].lNode, l, r, K, D);
if (r >= node[node[xNode].rNode].l) Modify(node[xNode].rNode, l, r, K, D);
return;
}
long long Query(int xNode, int p) {
if (node[xNode].l == node[xNode].r) return node[xNode].val + node[xNode].K;
if (node[xNode].tag) PushDown(xNode);
long long ret = 0;
if (p <= node[node[xNode].lNode].r) ret += Query(node[xNode].lNode, p);
if (p >= node[node[xNode].rNode].l) ret += Query(node[xNode].rNode, p);
ret += node[xNode].K;
ret += node[xNode].D * (p - node[xNode].l);
return ret;
}
例4：P1253 [yLOI2018] 扶苏的问题
需要注意的是，因为可能赋值为 $0$ 或负数，所以需要用一个不可能出现的数来表示不存在。
例5：P3373 【模板】线段树 2
标记的下传顺序十分关键：在 $\text{pushdown}$ 时，必须先下传乘法标记，再下传加法标记。因为乘法标记在下传时，需要让子节点的加法标记也乘上当前节点的乘法标记值，如果先下传加法标记，会让下传的那部分加法标记再乘上乘法标记，而事实上这部分标记已经在原节点乘过了，因此会计算错误。
例6：P4513 小白逛公园
最大字段和。
void PushUp(Node &xNode, Node lNode, Node rNode) {
xNode.res = std::max(lNode.res, rNode.res);
xNode.res = std::max(lNode.suf + rNode.pre, xNode.res);
xNode.pre = std::max(lNode.val + rNode.pre, lNode.pre);
xNode.suf = std::max(lNode.suf + rNode.val, rNode.suf);
xNode.val = lNode.val + rNode.val;
return;
}
Node Query(int xNode, int a, int b) {
if (a <= node[xNode].l && node[xNode].r <= b) return node[xNode];
if (b <= node[node[xNode].lNode].r) return Query(node[xNode].lNode, a, b);
if (a >= node[node[xNode].rNode].l) return Query(node[xNode].rNode, a, b);
Node ret;
Node lNode = Query(node[xNode].lNode, a, b);
Node rNode = Query(node[xNode].rNode, a, b);
PushUp(ret, lNode, rNode);
return ret;
}
双倍经验
- SP1716
权值线段树
对一个数列 $a$ 构造一个数列 $b$，其中 $b_i$ 表示 $a$ 中数值 $i$ 出现的次数，也即 $a_j = i$ 的 $j$ 的个数，这样的数列 $b$ 称作数列 $a$ 的权值数列，对 $b$ 构造的线段树成为 $a$ 的权值线段树。
权值线段树在很多计数问题中有着重要的应用，因为它可以轻松地修改对 $a$ 维护的统计信息。容易发现，当将 $a_i$ 从 $x$ 修改为 $y$ 时，只需要对其权值线段树做两次单点修改，即给 $b_x$ 减去 $1$，给 $b_y$ 加上 $1$。