【数据结构】线段树算法总结（单点修改）

知识概览

用作单点修改的线段树有4个操作：

1. pushup：由子节点的信息计算父节点的信息
2. build：初始化一棵树
3. modify：修改一个区间
4. query：查询一个区间

 线段树用一维数组来存储：

• 编号是x的节点，它的父节点是，左儿子是2x，右儿子是2x+1。

线段树的应用范围如下：

• 线段树相对于树状数组，常数比较大。但是，线段树用途广泛，可以解决许多区间修改，区间查询的问题。而树状数组的本质是可以解决单点修改，区间查询前缀和的问题。 

带懒标记（支持区间修改）的线段树算法见本人博客：【数据结构】线段树算法总结（区间修改）-CSDN博客【代码总结】线段树算法总结（区间修改）https://blog.csdn.net/u012181348/article/details/135120038?spm=1001.2014.3001.5501

 

例题展示

题目链接 

1275. 最大数 - AcWing题库https://www.acwing.com/problem/content/1277/

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;const int N = 200010;int m, p;
struct Node
{int l, r;int v;  // 区间[l, r]中的最大值
} tr[N * 4];void pushup(int u)  // 由子节点的信息，来计算父节点的信息
{tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}void build(int u, int l, int r)
{tr[u] = {l, r};if (l == r) return;int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}int query(int u, int l, int r)
{if (tr[u].l >= l && tr[u].r <= r) return tr[u].v;  // 树中节点，已经被完全包含在[l, r]中了int mid = tr[u].l + tr[u].r >> 1;int v = 0;if (l <= mid) v = query(u << 1, l, r);if (r > mid) v = max(v, query(u << 1 | 1, l, r));return v;
}void modify(int u, int x, int v)
{if (tr[u].l == x && tr[u].r == x) tr[u].v = v;else{int mid = tr[u].l + tr[u].r >> 1;if (x <= mid) modify(u << 1, x, v);else modify(u << 1 | 1, x, v);pushup(u);}
}int main()
{int n = 0, last = 0;scanf("%d%d", &m, &p);build(1, 1, m);int x;char op[2];while (m--){scanf("%s%d", op, &x);if (*op == 'Q'){last = query(1, n - x + 1, n);printf("%d\n", last);}else{modify(1, n + 1, ((LL)last + x) % p);n++;}}return 0;
}

题目链接

245. 你能回答这些问题吗 - AcWing题库高质量的算法题库https://www.acwing.com/problem/content/246/

题解

横跨左右子区间的最大子段和 = 左子区间的最大后缀 + 右子区间的最大前缀，需要在线段树节点中添加附加信息。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 500010;int n, m;
int w[N];
struct Node
{int l, r;int sum, lmax, rmax, tmax;
} tr[N * 4];void pushup(Node &u, Node &l, Node &r)
{u.sum = l.sum + r.sum;u.lmax = max(l.lmax, l.sum + r.lmax);u.rmax = max(r.rmax, r.sum + l.rmax);u.tmax = max(max(l.tmax, r.tmax), l.rmax + r.lmax);
}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, w[r], w[r], w[r], w[r]};else{tr[u] = {l, r};int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);pushup(u);}
}int modify(int u, int x, int v)
{if (tr[u].l == x && tr[u].r == x) tr[u] = {x, x, v, v, v, v};else{int mid = tr[u].l + tr[u].r >> 1;if (x <= mid) modify(u << 1, x, v);else modify(u << 1 | 1, x, v);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{auto left = query(u << 1, l, r);auto right = query(u << 1 | 1, l, r);Node res;pushup(res, left, right);return res;}}
}int main()
{scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) scanf("%d", &w[i]);build(1, 1, n);int k, x, y;while (m--){scanf("%d%d%d", &k, &x, &y);if (k == 1){if (x > y) swap(x, y);printf("%d\n", query(1, x, y).tmax);}else modify(1, x, y);}return 0;
}

参考资料

1. AcWing算法提高课