目录
线段树
定义
线段树是一种用于区间查询和更新问题的数据结构。它通过递归地将一个区间分解为若干子区间，每个节点代表一个子区间的和、最小值、最大值等信息，从而能够在O(log n)时间内完成单点更新和区间查询的操作。线段树的节点数目最多为4n，其中n是原始数组的长度。
运用情况
- 区间求和：例如，查询给定区间内所有元素的总和。
- 区间最值：找出给定区间内的最大值或最小值。
- 区间修改：对给定区间内的所有元素进行统一的增加或减少操作。
- 区间统计：统计区间内满足某种条件的元素数量。
- 懒惰传播：当区间修改操作较多时，可以使用懒惰传播优化，避免不必要的节点更新。
注意事项
- 初始化：在构建线段树时，需要为每个节点初始化适当的默认值。
- 索引范围：线段树的索引通常从1开始，而非从0开始，以简化递归过程中的边界处理。
- 更新操作：单点更新时，需要从叶子节点向上更新至根节点，确保所有受影响的区间节点都得到正确的值。
- 查询操作：区间查询时，可能需要合并多个子区间的值，这要求节点存储的信息支持合并操作。
解题思路
- 构建线段树：从底层（叶子节点）开始，向上层（根节点）逐步构建，每个节点的值由其子节点的值决定。
- 区间查询：从根节点开始，根据查询区间向下遍历，将查询区间分解为线段树中几个不相交的子区间，最终将子区间的值合并得到查询结果。
- 区间更新：对于区间更新操作，可以使用懒惰传播技术，只在必要时更新节点值，避免在每次更新时遍历整个区间。
AcWing 245. 你能回答这些问题吗
题目描述
运行代码
#include <iostream>
#include <cstring>
const int N = 5E5 + 10;
int n, m;
int a[N];
struct Node
{
int l, r;
int sum, lm, rm, tm;
} tr[N << 2];
void pushup(Node &u, Node &l, Node &r)
{
u.sum = l.sum + r.sum;
u.lm = std::max(l.lm, l.sum + r.lm);
u.rm = std::max(r.rm, r.sum + l.rm);
u.tm = std::max(std::max(l.tm, r.tm), l.rm + r.lm);
}
void pushup(int u)
{
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r)
{
if (l == r)
{
tr[u] = {l, r, a[l], a[l], a[l], a[l]};
}
else
{
tr[u] = {l, r};
int mid = (l + r) >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int x, int y)
{
if (tr[u].l == x && tr[u].r == x)
{
tr[u] = {x, x, y, y, y, y};
}
else
{
int mid = (tr[u].l + tr[u].r) >> 1;
if (x <= mid)
modify(u << 1, x, y);
else
modify(u << 1 | 1, x, y);
pushup(u);
}
}
Node query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r)
return tr[u];
else
{
int mid = (tr[u].l + tr[u].r) >> 1;
if (r <= mid)
return query(u << 1, l, r);
else if (l > mid)
return query(u << 1 | 1, l, r);
else
{
Node left = query(u << 1, l, r);
Node right = query(u << 1 | 1, l, r);
Node res;
pushup(res, left, right);
return res;
}
}
}
int main()
{
std::cin >> n >> m;
for (int i = 1; i <= n; i++)
std::cin >> a[i];
build(1, 1, n);
while (m--)
{
int k, x, y;
std::cin >> k >> x >> y;
if (k == 1)
{
if (x > y)
std::swap(x, y);
std::cout << query(1, x, y).tm << std::endl;
}
else
{
modify(1, x, y);
}
}
}代码思路
数据结构定义：
Node结构体定义了线段树节点所携带的信息，包括：l和r：节点代表的区间的左右端点。sum：区间内所有数值的总和。lm和rm：以区间左侧或右侧为结尾的最大子数组和。tm：区间内的最大子数组和。
主要函数说明：
-
pushup：用于更新父节点的信息，根据左右子节点的信息计算父节点的sum、lm、rm和tm。 -
build：构建线段树，从叶子节点开始，递归地向上构建，直到根节点。 -
modify：用于更新线段树中某个位置的值，递归地找到叶子节点并更新，然后递归返回时更新所有经过的父节点。 -
query：用于查询某个区间内的最大子数组和，递归地查找区间对应的子树，并在返回时计算最大子数组和。
主函数流程：
- 输入读取：读取数组的长度
n和操作次数m，接着读取数组a的值。 - 构建线段树：使用
build函数构建线段树。 - 处理操作：对于每一次操作，如果操作类型为1，则执行区间查询，输出该区间内的最大子数组和；如果操作类型为2，则更新某个位置的值。
改进思路
1.代码清晰度和可读性
命名规范：可以改进变量名和函数名，使其更具描述性，比如将 tr 改为 tree，将 lm、rm 和 tm 改为更具描述性的名称，如 leftMaxSum、rightMaxSum 和 totalMaxSum。
注释：添加更多的注释来解释代码的意图和关键步骤，这有助于其他开发者理解和维护代码。
2. 模块化
分离函数职责：将 pushup 函数分为两个，一个用于更新 sum、leftMaxSum 和 rightMaxSum，另一个专门用于更新 totalMaxSum。这样可以提高代码的模块化和可读性。
3. 异常处理和边界条件
输入验证：增加对输入数据的验证，确保 n 和 m 的值在合理范围内，以及操作中的 x 和 y 不超出数组边界。
空操作处理：在 modify 和 query 函数中，当操作的区间为空（如 x > y）时，应有相应的处理逻辑。
4. 性能优化
懒惰传播：如果更新操作频繁且范围较大，可以引入懒惰传播机制来延迟更新，直到真正需要时才进行，这可以显著减少更新操作的时间复杂度。
查询优化：虽然当前的查询实现已经足够高效，但在处理大量查询时，可以考虑缓存部分结果以减少重复计算。
5. 代码复用性
泛型模板：如果可能，可以将线段树实现封装为模板类，使其能够处理不同类型的数值，提高代码的复用性。
6. 安全性
溢出处理：在处理大数值时，确保不会发生整数溢出，尤其是在计算区间和或最大子数组和时。