当前位置：首页 > news >正文

网站建设用啥系统好宁波企业制作网站

news 2025/9/16 13:33:55

网站建设用啥系统好,宁波企业制作网站,移动网站构建,北京城建一建设发展有限公司网站知识概览用作单点修改的线段树有4个操作： pushup：由子节点的信息计算父节点的信息build：初始化一棵树modify：修改一个区间query：查询一个区间线段树用一维数组来存储： 编号是x的节点，它的父节…

知识概览

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

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

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

编号是x的节点，它的父节点是 $\left \lfloor \frac{x}{2} \right \rfloor$ ，左儿子是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;
}