线段树自我总结

题目链接P3372 【模板】线段树 1 - 洛谷一.定义1.线段树是一棵由线段组成的树分治与二叉树的结合体2.线段树是一种二叉搜索树。什么叫做二叉搜索树首先满足二叉树每个结点度2即每个结点最多有两颗子树。何为搜索我们要知道线段树的每个结点都存储了一个区间也可以理解成一个线段而搜索就是在这些线段上进行搜索操作得到你想要的答案。二.特征1.用分治法自顶向下建立每次分治左右子树各一半。2.每个节点都表示一个“线段”区间非叶子节点包含多个元素叶子节点只包含一个元素。3.除了最后一层其他层都是满的。-----近似完全二叉树可以用数组存树。用一个数组tree[]存储节点。若一个节点的存储下标为k 则其左子节点的下标为2k 其右子节点的下标为2k 1。 4.lr说明这是一个叶子节点。5.lr说明他有两个子节点左儿子[l,m],右儿子[m1,r]其中m(lr)/2;三.作用线段树看起来挺麻烦的他为什么这么高效 每个结点的值代表了以它为根的子树上所有节点的值那么查询这个子树所代表的区间的值时就不必遍历整棵树而是直接读取这棵子树的根值就行了。并且树形结构的操作时间复杂度是O(logn)。 线段树最适合解决的问题的特征是大区间的解可以从小区间的解合并而来。 线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。 线段树可以在 O(log N) 的时间复杂度内实现单点修改、区间修改、区间查询区间求和求区间最大值求区间最小值等操作。四.建树首先我们得先明白几件事情。 每个结点存什么如何存树如何建树1一个结点对应一段区间[l,r]区间内有我们需要的值区间和最值等等所以一个结点内要保存该结点对应区间的左右边界需要的值。2线段树近似完全二叉树可以用数组存树。用一个数组tree[]存储节点。若一个节点的存储下标为o 则其左子节点的下标为2o 其右子节点的下标为2o 1。3建树以n个元素的区间(a[n])为基础建树。以维护区间和为例 tree[]数组大小4*n可能存在空间浪费) 基于递归建树。初始节点为1因为你要从1号节点开始建树。左子树节点是o*2右子树节点是o*21。线段树在构造子树时一个结点的两个子节点是平分这个子树的特征中说过在遍历时左子树范围是[l,m],右子树是 [m1,r],其中m(lr)/2。 线段树建树的时间复杂度为O(n)五.区间修改区间修改操作单点修改区间修改在一开始建树的时候该点是在树中的树中一个点改变可能会引起这棵树的改变。还是以区间求和为例当你改变了一个点这个点的所有父节点都得改变。如图先递归找到要修改的叶子节点直接修改叶子节点上元素的值然后从底往上更新线段树即可但是这样操作时间复杂度最坏是O(n)所以我们还需进行优化六.区间查询区间查询直接递归查询即可。但是在查询过程中要注意懒标记。 完全覆盖和部分覆盖两种情况无懒标记的线段树代码#include bits/stdc.h using namespace std; #define int long long #define endl \n int n, m; const int N 1e5 10; int a[N]; //线段树的结点结构 struct Node { int l, r; int sum; } tree[N 2]; void Build(int i, int le, int ri) // 构建第i号节点对应的区间[le,ri],时间复杂度O(n); {//建立线段树 tree[i].l le; tree[i].r ri; if(leri) {//区间中只有一个数据 叶子节点 tree[i].sum a[le]; return; } //区间中有多个数据 非叶子节点 int mid (le ri) / 2; Build(2 * i, le, mid); Build(2 * i 1, mid 1, ri); tree[i].sum tree[2 * i].sum tree[2 * i 1].sum; } void Update(int i,int le,int ri,int k) {//区间修改-最坏的情况下退化成O(n)--保持logn:懒标记 if(tree[i].ltree[i].r) {//叶子节点的修改 tree[i].sum k; return; } int mid (tree[i].l tree[i].r) / 2; if(lemid)//如果左孩子对应的区间有修改的部分先修改左孩子 { Update(2 * i, le, ri, k); } if(mid1ri)//如果右孩子对应的区间有修改的部分先修改右孩子 { Update(2 * i 1, le, ri, k); } tree[i].sum tree[2 * i].sum tree[2 * i 1].sum; } int query(int i,int le,int ri) {//查询[le,ri] int ans 0; if(tree[i].lletree[i].rri){ //第i个节点对应的区间被查询的区间完全覆盖第i个节点对应的区间和要被算到答案里面 return tree[i].sum; } else {//第i个节点对应的区间没有被查询的区间完全覆盖 int mid (tree[i].l tree[i].r) / 2; if(lemid) { ans query(2 * i, le, ri); } if(rimid1) { ans query(2 * i 1, le, ri); } return ans; } } void solve() { cin n m; for (int i 1; i n;i) { cin a[i]; } Build(1, 1, n); // 从根节点开始建树 根节点1号节点[1,n]; int q, x, y, k; while(m--){ cin q; if(q1) { cin x y k; Update(1, x, y, k); } else { cin x y; int ans query(1, x, y); cout ans endl; } } } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T 1; // cin T; while (T--) { solve(); } return 0; }七.懒标记为了降低时间复杂度我们引进一个新玩意lazy-tag懒标记。tag[i]记录了区间i的修改这样就不用一个一个的再去修改去区间的内的每个元素了。也可以直接在结构体中加tag属性。 那啥时候修改一会再修改。 既然不一个个的改那我们就改整体 当我们进行修改时先只对这个线段区间上进行整体上的修改其内部每个元素的值先不修改。只有当查找到的区间[l,r]不包含在给定的区间[L,R]时即lL||rR时才把变化值传给下一层的子区间即修改内部元素。完全覆盖部分覆盖八.down函数down这个函数也就是当需要查询某个结点的子树时需要用到这个函数函数功能就是更新子树的lazy值可以理解为平时先把事情放着等到哪天要检查的时候就临时再去做而且做也不是一次性做完检查哪一部分它就只做这一部分。是不是感受到了什么是Lazy_tag实至名归带有懒标记的线段树#include bits/stdc.h using namespace std; #define int long long #define endl \n int n, m; const int N 1e5 10; int a[N]; //线段树的结点结构 struct Node { int l, r; int sum; int lazy_tag; //lazy_tag0说明该节点对应的区间没有被修改过!0被修改过 } tree[N 2]; void pushup(int i) {//合并左右子节点的信息到父节点 tree[i].sum tree[2 * i].sum tree[2 * i 1].sum; } void Build(int i, int le, int ri) // 构建第i号节点对应的区间[le,ri],时间复杂度O(n); {//建立线段树 tree[i].l le; tree[i].r ri; if(leri) {//区间中只有一个数据 叶子节点 tree[i].sum a[le]; return; } //区间中有多个数据 非叶子节点 int mid (le ri) / 2; Build(2 * i, le, mid); Build(2 * i 1, mid 1, ri); pushup(i); } void apply(int i,int k) {//将懒标记应用到当前节点 tree[i].lazy_tag k; // 有可能连续多次修改 tree[i].sum (tree[i].r - tree[i].l 1) * k; } void pushdown(int i) { if (tree[i].lazy_tag ! 0) { apply(2 * i, tree[i].lazy_tag); apply(2 * i 1, tree[i].lazy_tag); tree[i].lazy_tag 0; } } void Update(int i, int le, int ri, int k) { // 引入懒标记-保持在O(logn); if(tree[i].lletree[i].rri) {//第i个节点对应的区间被要修改的区间完全覆盖 apply(i, k); return; } else { pushdown(i);//下传懒标记把第i个节点的两个孩子对应的区间把之前欠的先修改了 int mid (tree[i].l tree[i].r) / 2; if(lemid) { Update(2 * i, le, ri, k); } if(rimid1) { Update(2 * i 1, le, ri, k); } pushup(i); } } int query(int i, int le, int ri) { // 查询[le,ri] int ans 0; if (tree[i].l le tree[i].r ri) { // 第i个节点对应的区间被查询的区间完全覆盖第i个节点对应的区间和要被算到答案里面 return tree[i].sum; } else { // 第i个节点对应的区间没有被查询的区间完全覆盖 pushdown(i); // 下传懒标记把第i个节点的两个孩子对应的区间把之前欠的先修改了 int mid (tree[i].l tree[i].r) / 2; if (le mid) { ans query(2 * i, le, ri); } if (ri mid 1) { ans query(2 * i 1, le, ri); } return ans; } } void solve() { cin n m; for (int i 1; i n;i) { cin a[i]; } Build(1, 1, n); // 从根节点开始建树 根节点1号节点[1,n]; int q, x, y, k; while(m--){ cin q; if(q1) { cin x y k; Update(1, x, y, k); } else { cin x y; int ans query(1, x, y); cout ans endl; } } } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T 1; // cin T; while (T--) { solve(); } return 0; }