线段树算法(C++/C)

news/2024/11/6 9:36:51/

目录​​​​​​​

一、线段树算法的概念

二、为什么需要线段树

三、线段树算法的实现

(1)建树

(2)查询

(3)修改

(4)综合代码,求区间和

(5)综合代码,求区间最大值

四、Lazy标记


一、线段树算法的概念

线段树(Segment Tree)是一种基于二分思想的数据结构,常常用于处理区间查询和区间修改。线段树的常用操作包括建树、查询、修改。

线段树的建树过程可以使用递归实现,也可以使用非递归实现(通常使用栈来实现)。

线段树的查询和修改基本都是从根节点开始,往下遍历到叶子节点或者与查询区间(或修改区间)不相交的节点为止。线段树相关问题经常需要使用懒惰标记(Lazy Tag)来优化。

线段树常用于以下场景:区间最值查询、区间求和、区间修改等

二、为什么需要线段树

考虑这样两个场景:

  1. 对于一个长度为 n 的数组,现在给定 l,r 让你求 l 到 r 所有元素的和,有多个这样的询问.
  2. 对于一个长度为 n 的数组,现在对数组的第 k 个元素进行修改后,给定 l,r 让你求 l 到 r 所有元素的和,有多个这样的询问.

大家看到第一种情况的时候,这不就是前缀和,是的.第二种情况呢,前缀和还能不能用,显然每次修改之后,前缀和就不能使用了,所以又退化为 O(n) 的时间复杂度了.

此时我们就需要用到我们的线段树了.

对于线段树中的每一个非叶子节点[a,b],它的左儿子表示的区间为[a,(a+b)/2],右儿子表示的区间为[(a+b)/2+1,b]。最后的子节点数目为 N,即整个线段区间的长度。

我们看一下 1-10 的线段树是如何存储的.

三、线段树算法的实现

(1)建树

void build(int p, int l, int r) {t[p].l = l, t[p].r = r; // 节点p代表区间[l,r]if (l == r) { t[p].dat = a[l]; return; } // 叶节点int mid = (l + r) / 2; // 折半build(p*2, l, mid); // 左子节点[l,mid],编号p*2build(p*2+1, mid+1, r); // 右子节点[mid+1,r],编号p*2+1// t[p].dat = max(t[p*2].dat, t[p*2+1].dat); // 从下往上传递信息t[p].dat = t[p*2].dat+t[p*2+1].dat; // 从下往上传递信息
}

(2)查询

int ask(int p, int l, int r) {if (l <= t[p].l && r >= t[p].r) return t[p].dat; // 完全包含,直接返回int mid = (t[p].l + t[p].r) / 2;int val = 0;if (l <= mid) val = val+ ask(p*2, l, r); // 左子节点有重叠if (r > mid) val = val+ask(p*2+1, l, r); // 右子节点有重叠return val;
}

(3)修改

void change(int p, int x, int v) {if (t[p].l == t[p].r) { t[p].dat = v; return; } // 找到叶节点int mid = (t[p].l + t[p].r) / 2;if (x <= mid) change(p*2, x, v); // x属于左半区间else change(p*2+1, x, v); // x属于右半区间// t[p].dat = max(t[p*2].dat, t[p*2+1].dat); // 从下往上更新信息t[p].dat = t[p*2].dat+t[p*2+1].dat;
}

(4)综合代码,求区间和

#include<bits/stdc++.h>
using namespace std;const int SIZE=11;int a[11]={0,1,2,3,4,5,6,7,8,9,10}; //原始数据struct SegmentTree {int l, r;int dat;
} t[SIZE * 4]; // struct数组存储线段树void build(int p, int l, int r) {t[p].l = l, t[p].r = r; // 节点p代表区间[l,r]if (l == r) { t[p].dat = a[l]; return; } // 叶节点int mid = (l + r) / 2; // 折半build(p*2, l, mid); // 左子节点[l,mid],编号p*2build(p*2+1, mid+1, r); // 右子节点[mid+1,r],编号p*2+1// t[p].dat = max(t[p*2].dat, t[p*2+1].dat); // 从下往上传递信息t[p].dat = t[p*2].dat+t[p*2+1].dat; // 从下往上传递信息
}void change(int p, int x, int v) {if (t[p].l == t[p].r) { t[p].dat = v; return; } // 找到叶节点int mid = (t[p].l + t[p].r) / 2;if (x <= mid) change(p*2, x, v); // x属于左半区间else change(p*2+1, x, v); // x属于右半区间// t[p].dat = max(t[p*2].dat, t[p*2+1].dat); // 从下往上更新信息t[p].dat = t[p*2].dat+t[p*2+1].dat;
}int ask(int p, int l, int r) {if (l <= t[p].l && r >= t[p].r) return t[p].dat; // 完全包含,直接返回int mid = (t[p].l + t[p].r) / 2;int val = 0;if (l <= mid) val = val+ ask(p*2, l, r); // 左子节点有重叠if (r > mid) val = val+ask(p*2+1, l, r); // 右子节点有重叠return val;
}
int main()
{//建树从根节点一点一点往下建立,所以第一个参数就是1号编号build(1,1,10);//查询区间[4,7]的和,第一个参数是1的原因是查询要从根节点开始递归int ans=ask(1,4,7);cout<<ans;//修改位置4的值变为25,第一个参数是1的原因是修改也要从根节点开始一步一步往下进行修改change(1,4,25);ans=ask(1,4,7);cout<<ans;return 0;}

(5)综合代码,求区间最大值

#include<bits/stdc++.h>
using namespace std;const int SIZE=11;int a[11]={0,1,2,3,4,5,6,7,8,9,10}; //原始数据struct SegmentTree {int l, r;int dat;
} t[SIZE * 4]; // struct数组存储线段树void build(int p, int l, int r) {t[p].l = l, t[p].r = r; // 节点p代表区间[l,r]if (l == r) { t[p].dat = a[l]; return; } // 叶节点int mid = (l + r) / 2; // 折半build(p*2, l, mid); // 左子节点[l,mid],编号p*2build(p*2+1, mid+1, r); // 右子节点[mid+1,r],编号p*2+1// t[p].dat = max(t[p*2].dat, t[p*2+1].dat); // 从下往上传递信息t[p].dat = max( t[p * 2].dat , t[p * 2 + 1].dat); // 从下往上传递信息
}void change(int p, int x, int v) {if (t[p].l == t[p].r) { t[p].dat = v; return; } // 找到叶节点int mid = (t[p].l + t[p].r) / 2;if (x <= mid) change(p*2, x, v); // x属于左半区间else change(p*2+1, x, v); // x属于右半区间// t[p].dat = max(t[p*2].dat, t[p*2+1].dat); // 从下往上更新信息t[p].dat = max( t[p * 2].dat , t[p * 2 + 1].dat);
}int ask(int p, int l, int r) {if (l <= t[p].l && r >= t[p].r) return t[p].dat; // 完全包含,直接返回int mid = (t[p].l + t[p].r) / 2;int val = 0;if (l <= mid) val = max(val, ask(p * 2, l, r)); // 左子节点有重叠if (r > mid) val =  max(val, ask(p * 2 + 1, l, r)); // 右子节点有重叠return val;
}
int main()
{build(1,1,10);int ans=ask(1,4,7);cout<<ans;change(1,4,25);ans=ask(1,4,7);cout<<ans;return 0;}

四、Lazy标记

这种类型的题目,一般都是这样问的:如果每次是对一个区间进行修改,比如让 l,r 区间内的每个值都加 30.然后求和。

如果我们换成对于点的修改,那么时间复杂就太高了.那我们怎么办呢?

我们可以使用 Lazy 标记的方式,进行处理,什么是 Lazy 标记?

若在一次修改操作中发现节点 p 所代表的区间 [pl​,pr​] 被修改区间 [l,r] 完全覆盖,并且随后的查询操作没有利用到范围 [l,r] 的子区间作为候选答案,那么对节点 p 及其子树进行的更新操作将是没有实际效果的。此情况下,我们需要考虑优化算法,避免对整棵子树进行无意义的更新。

在执行修改指令时,如果发现存在 l < pl​ < pr​ < r 的情况,可以立即返回,并在回溯之前向节点 p 添加一个 Lazy 标记,用于表示 '该节点曾被修改,但其子节点尚未被更新'。

在后续的指令中,若需要向下递归至节点 p,应检查节点 p 是否带有标记。如果存在标记,应根据标记信息更新节点 p 的两个子节点,并为这两个子节点添加标记。然后清除节点 p 的标记。

除了在修改指令中直接划分成的 O(logN) 个节点外,对任意节点的修改都延迟到 '在后续操作中递归进入它的父节点时' 再执行。这样一来,每条查询或修改指令的时间复杂度都降低到了 O(logN)。我们将这些标记称为 '延迟标记',它们提供了线段树中从上往下传递信息的方式。通过延迟标记的设计,我们能够更加高效地处理线段树操作。

这种 '延迟' 的思想是设计算法与解决问题时的一个重要思路,它充分利用了操作的特性,避免了不必要的计算,并提升了算法的效率。延迟标记的应用为线段树操作提供了一种优化策略,使得算法的时间复杂度得以降低。

那我们该如何设计呢.

#include <bits/stdc++.h>
using namespace std;const int SIZE = 11;int a[11] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // 原始数据struct SegmentTree
{int l, r;long long sum, add;
} tree[SIZE * 4]; // struct数组存储线段树void build(int p, int l, int r)
{tree[p].l = l, tree[p].r = r;if (l == r){tree[p].sum = a[l];return;}int mid = (l + r) / 2;build(p * 2, l, mid);          // 构建左子树build(p * 2 + 1, mid + 1, r);  // 构建右子树tree[p].sum = tree[p * 2].sum + tree[p * 2 + 1].sum;  // 更新节点的区间和
}void spread(int p)
{// 下传延迟标记if (tree[p].add){tree[p * 2].sum += tree[p].add * (tree[p * 2].r - tree[p * 2].l + 1);tree[p * 2 + 1].sum += tree[p].add * (tree[p * 2 + 1].r - tree[p * 2 + 1].l + 1);tree[p * 2].add += tree[p].add;     // 左子树打延迟标记tree[p * 2 + 1].add += tree[p].add; // 右子树打延迟标记tree[p].add = 0;                    // 清除延迟标记}
}void change(int p, int l, int r, int d)
{if (l <= tree[p].l && r >= tree[p].r){// 完全覆盖节点的区间tree[p].sum = (long long)d * (tree[p].r - tree[p].l + 1);  // 更新节点的区间和tree[p].add += d;                                         // 打延迟标记return;}spread(p);int mid = (tree[p].l + tree[p].r) / 2;if (l <= mid)change(p * 2, l, r, d);         // 修改左子树if (r > mid)change(p * 2 + 1, l, r, d);     // 修改右子树tree[p].sum = tree[p * 2].sum + tree[p * 2 + 1].sum;  // 更新节点的区间和
}long long ask(int p, int l, int r)
{if (l <= tree[p].l && r >= tree[p].r)return tree[p].sum;spread(p);int mid = (tree[p].l + tree[p].r) / 2;long long val = 0;if (l <= mid)val += ask(p * 2, l, r);          // 查询左子树if (r > mid)val += ask(p * 2 + 1, l, r);      // 查询右子树return val;
}int main()
{build(1, 1, 10);int ans = ask(1, 4, 7);cout << ans << endl;change(1, 4, 5, 10);ans = ask(1, 4, 7);cout << ans << endl;return 0;
}

 


http://www.ppmy.cn/news/189689.html

相关文章

Api-免费新闻资讯接口

接口简介&#xff1a; 该新闻资讯接口数据来源均来自互联网&#xff0c;您在使用接口数据时产生的版权责任我们不承担责任。 子接口&#xff1a; 获取新闻 新闻频道获取 接口地址&#xff1a;www.idmayi.com(支持:http/https) 返回格式&#xff1a; json,xml 请求方式&#xff…

怎么下载央视网的视频到本地?

第一步&#xff1a;首先进入我们想要下载的界面&#xff0c;打开开发者工具(F12)。 第二步&#xff1a;单击Network,再单击All,按F5刷新。找到名称为getHttpVideo......的项目&#xff0c;复制它的URL。 第三步&#xff1a;在浏览器顶端输入该URL&#xff0c;在弹出的网页中&a…

新闻资讯类网站

有技术支持https://yunbaowangluo.cn

发布一款新闻资讯软件(android版)

这款软件经历了半个月的开发现在终于有点像样了&#xff0c;才展示给大家。希望有兴趣的朋友可以尝试用一下这款软件。我已经将软件上传到我的资源里面&#xff0c;以下为截图 首页启动界面一个传统的九宫格界面&#xff0c;触摸屏幕可以左右滑动来翻页 天气查询&#xff0c;可…

帝国CMS金融财经新闻资讯门户网站源码 PC+WAP手机版

介绍&#xff1a; 帝国CMS金融财经新闻资讯门户网站源码 PCWAP手机版 网盘下载地址&#xff1a; http://kekewl.net/wyHvrIZ7NON0 图片&#xff1a;

怎么搜索到最新最全的热点新闻资讯呢?有这四个工具就够了

怎么第一时间搜索到最新最全的热点新闻资讯呢&#xff1f;我们经常可以看到一个新闻会从不同的角度去报道&#xff0c;也充分说明热点是可以帮助你的文章获得更多曝光的&#xff0c;下面就跟大家讲讲可以从哪些平台上找到热点、爆款资讯呢&#xff1f; 01 135编辑器——实时热点…

android今日资讯代码,今日资讯app下载_今日资讯新闻弹窗最新消息软件下载安装 安卓版 V1.4 - 罐头安卓网...

今日资讯app是一款拥有海量新闻实时资讯的手机软件&#xff0c;帮助用户实时了解海内外热门新闻以及重要政治要闻&#xff0c;聚集了全国各地的资讯新闻信息内容&#xff0c;祝你轻松搞定一切热点新闻讯息。在这里所有报道全部都是权威性资讯文章&#xff0c;专业又严谨&#x…