网站建设按钮,品牌设计网站大全,网络教学平台昆明理工大学,萍乡土建设计网站知识概览
用作单点修改的线段树有4个操作#xff1a; pushup#xff1a;由子节点的信息计算父节点的信息build#xff1a;初始化一棵树modify#xff1a;修改一个区间query#xff1a;查询一个区间 线段树用一维数组来存储#xff1a; 编号是x的节点#xff0c;它的父节…知识概览
用作单点修改的线段树有4个操作 pushup由子节点的信息计算父节点的信息build初始化一棵树modify修改一个区间query查询一个区间 线段树用一维数组来存储 编号是x的节点它的父节点是左儿子是2x右儿子是2x1。 线段树的应用范围如下 线段树相对于树状数组常数比较大。但是线段树用途广泛可以解决许多区间修改区间查询的问题。而树状数组的本质是可以解决单点修改区间查询前缀和的问题。 带懒标记支持区间修改的线段树算法见本人博客【数据结构】线段树算法总结区间修改-CSDN博客【代码总结】线段树算法总结区间修改https://blog.csdn.net/u012181348/article/details/135120038?spm1001.2014.3001.5501 例题展示
题目链接
1275. 最大数 - AcWing题库https://www.acwing.com/problem/content/1277/
代码
#include cstdio
#include cstring
#include iostream
#include algorithmusing 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 algorithmusing 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;
} 参考资料
AcWing算法提高课
