线段树

文章目录

  • 1 线段树概念
  • 2 线段树操作
    • 2.1 建树
    • 2.2 区间修改
    • 2.3 区间查询
    • 2.4 练习题目
  • 3 线段树进阶
    • 3.1 乘法线段树
  • * 补充：快读快写
  • 4 End

1 线段树概念

线段树 ( S e g m e n t   T r e e ) (Segment\ Tree) (Segment Tree) 是 O I OI OI 中的常用算法。线段树是一种二叉搜索树，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。且时间复杂度仅 Θ ( log ⁡ n ) \varTheta(\log n) Θ(logn)。

2 线段树操作

2.1 建树

对于一个区间，我们可以把它用线段树存储。可以把区间 [ 1 , 4 ] [1,4] [1,4] 用如图所示的方式存储：

11 线段树示意

也就是说，如果要求 [ 1 , 4 ] [1,4] [1,4] 的区间和，就可以通过把这个节点的两个儿子 [ 1 , 2 ] [1,2] [1,2] 和 [ 3 , 4 ] [3,4] [3,4] 的权值相加得到。推导到一般式，即

t r e e i . s u m = t r e e i × 2 . s u m + t r e e i × 2 + 1 . s u m tree_i.sum = tree_{i \times 2}.sum + tree_{i \times 2 + 1}.sum treei​.sum=treei×2​.sum+treei×2+1​.sum

struct segment_tree{
    int sum, tag = 0, l, r;
}tree[N << 2];
inline void build(int i, int l, int r) {
    tree[i].l = l, tree[i].r = r;
    if (l == r) {
        tree[i].sum = a[l];
        return;
    } 
    int mid = (l + r) >> 1;
    build(i << 1, l, mid);
    build(i << 1 | 1, mid + 1, r);
    tree[i].sum = tree[i << 1].sum + tree[i << 1 | 1].sum;
}

注意线段树要开四倍空间。

2.2 区间修改

对给定区间每个数增加 k k k。这个似乎有一点棘手，我们可以引入一个新的懒标记 ( L a z y T a g ) (Lazy Tag) (LazyTag)。一个点的懒标记代表它的区间上所有点应当做出的修改。

以 § 1 \texttt§1 §1 中的图为例，例如修改 [ 1 , 3 ] [1,3] [1,3] 的值，从 [ 1 , 4 ] [1,4] [1,4] 向下找，它的左儿子 [ 1 , 2 ] [1,2] [1,2] 显然包含在所要修改的区间之内；它的右儿子 [ 3 , 4 ] [3,4] [3,4] 区间过大，从它的左儿子接着找： [ 3 , 3 ] [3,3] [3,3] 在区间中，而 [ 4 , 4 ] [4,4] [4,4] 不在区间中。所以，只需要把 [ 1.2 ] [1.2] [1.2] 和 [ 3 , 3 ] [3,3] [3,3] 标记。

推导到一般地，如果区间包含在修改区间中，那么它需要打标记；如果不包含，考虑儿子：左儿子在区间中，找左儿子；右儿子在区间中，找右儿子。

如果单纯这样想，显然有一个巨大的纰漏：比如我们修改了 [ 1 , 3 ] [1,3] [1,3]，然后通过查询操作查询了 [ 1 , 3 ] [1,3] [1,3] 的区间和，没有问题；但如果此时查询 [ 2 , 4 ] [2,4] [2,4]，因为 [ 2 , 2 ] [2,2] [2,2] 没有被打标记，所以会少加一个 k k k。

对于一个区间，如果整个区间都要修改，那么首先把点的权值增加 k × ( t r e e i . r − t r e e i . l + 1 ) k \times (tree_i.r - tree_i.l + 1) k×(treei​.r−treei​.l+1)。如果并不是都要修改，这时我们需要一个pushdown操作。所谓pushdown，就是把自己的懒标记清零，再给自己的儿子标记上。

inline void pushdown(int i) {
    if (tree[i].tag) {
        tree[i << 1].tag += tree[i].tag;
        tree[i << 1 | 1].tag += tree[i].tag;
        tree[i << 1].sum += tree[i].tag * (tree[i << 1].r - tree[i << 1].l + 1);
        tree[i << 1 | 1].sum += tree[i].tag * (tree[i << 1 | 1].r - tree[i << 1 | 1].l + 1);
        tree[i].tag = 0;
    }
}

其他的 t a g tag tag 不为 0 0 0 的区间在后面区间查询的时候顺便更新即可。区间修改的代码：

inline void add(int i, int l, int r, int k) {
    if (tree[i].l >= l && tree[i].r <= r) {
        tree[i].sum += k * (tree[i].r - tree[i].l + 1);
        tree[i].tag += k;
        return;
    }
    pushdown(i);
    if (tree[i << 1].r >= l) 
        add(i << 1, l, r, k);
    if (tree[i << 1 | 1].l <= r)
        add(i << 1 | 1, l, r, k);
    tree[i].sum = tree[i << 1].sum + tree[i << 1 | 1].sum;
}

2.3 区间查询

思路类似，注意pushdown即可。

inline int search(int i, int l, int r) {
    if (tree[i].l >= l && tree[i].r <= r) 
        return tree[i].sum;
    pushdown(i);
    int ans = 0;
    if (tree[i << 1].r >= l) 
        ans += search(i << 1, l, r);
    if (tree[i << 1 | 1].l <= r)
        ans += search(i << 1 | 1, l, r);
    return ans;
}

2.4 练习题目

【练习 2.1】P3372 【模板】线段树 1 - 洛谷 | 计算机科学教育新生态

题解

线段树模板题（注意要开 long   long \texttt{long long} long long）。

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const ll N = 2e5 + 10;
ll n, m, a[N];
struct segment_tree{
    ll sum, tag = 0, l, r;
}tree[N << 2];
inline void build(ll i, ll l, ll r) {
    tree[i].l = l, tree[i].r = r;
    if (l == r) {
        tree[i].sum = a[l];
        return;
    } 
    ll mid = (l + r) >> 1;
    build(i << 1, l, mid);
    build(i << 1 | 1, mid + 1, r);
    tree[i].sum = tree[i << 1].sum + tree[i << 1 | 1].sum;
}
inline void pushdown(ll i) {
    if (tree[i].tag) {
        tree[i << 1].tag += tree[i].tag;
        tree[i << 1 | 1].tag += tree[i].tag;
        tree[i << 1].sum += tree[i].tag * (tree[i << 1].r - tree[i << 1].l + 1);
        tree[i << 1 | 1].sum += tree[i].tag * (tree[i << 1 | 1].r - tree[i << 1 | 1].l + 1);
        tree[i].tag = 0;
    }
}
inline void add(ll i, ll l, ll r, ll k) {
    if (tree[i].l >= l && tree[i].r <= r) {
        tree[i].sum += k * (tree[i].r - tree[i].l + 1);
        tree[i].tag += k;
        return;
    }
    pushdown(i);
    if (tree[i << 1].r >= l) 
        add(i << 1, l, r, k);
    if (tree[i << 1 | 1].l <= r)
        add(i << 1 | 1, l, r, k);
    tree[i].sum = tree[i << 1].sum + tree[i << 1 | 1].sum;
}
inline ll search(ll i, ll l, ll r) {
    if (tree[i].l >= l && tree[i].r <= r) 
        return tree[i].sum;
    pushdown(i);
    ll ans = 0;
    if (tree[i << 1].r >= l) 
        ans += search(i << 1, l, r);
    if (tree[i << 1 | 1].l <= r)
        ans += search(i << 1 | 1, l, r);
    return ans;
}
int main() {
    cin >> n >> m;
    for (ll i = 1; i<= n; i++) 
        cin >> a[i];
    build(1, 1, n);
    while (m--) {
        ll op, x, y, k;
        cin >> op;
        if (op == 1) {
            cin >> x >> y >> k;
            add(1, x, y, k);
        } else {
            cin >> x >> y;
            cout << search(1, x, y) << endl;
        }
    }
    return 0;
}

3 线段树进阶

3.1 乘法线段树

如果线段树只有乘法操作，那么只要让懒标记变成乘法，然后 tree[i].sum *= k 即可。

但如果是有乘法也有加法，我们需要考虑先加还是先乘。

把懒标记分成加法标记 ( p l z ) (plz) (plz) 和乘法标记 ( m l z ) (mlz) (mlz)。对于 m l z mlz mlz，直接乘上父亲的标记即可，而对于 p l z plz plz，需要把原先的 p l z plz plz 乘上父亲的 m l z mlz mlz 再加上父亲的 p l z plz plz。

【练习 3.1】P3373 【模板】线段树 2 - 洛谷 | 计算机科学教育新生态

题解

乘法线段树模板题（注意要开 long   long \texttt{long long} long long 和取模）。

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const ll N = 2e5 + 10;
ll n, m, q, a[N];
struct segment_tree{
    ll sum, plz, mlz, l, r;
}tree[N << 2];
inline ll mod(ll x){
    return (x % m + m) % m;
}
inline void build(ll i, ll l, ll r) {
    tree[i].l = l, tree[i].r = r;
    tree[i].plz = 0, tree[i].mlz = 1;
    if (l == r) {
        tree[i].sum = a[l];
        return;
    } 
    ll mid = (l + r) >> 1;
    build(i << 1, l, mid);
    build(i << 1 | 1, mid + 1, r);
    tree[i].sum = mod(tree[i << 1].sum + tree[i << 1 | 1].sum);
}
inline void pushdown(ll i) {
    if (tree[i].plz == 0 && tree[i].mlz == 1) 
        return;
    int mlz0 = tree[i].mlz, plz0 = tree[i].plz;
    tree[i << 1].sum = mod(tree[i << 1].sum * mlz0 + plz0 * (tree[i << 1].r - tree[i << 1].l + 1));
    tree[i << 1].mlz = mod(tree[i << 1].mlz * mlz0);
    tree[i << 1].plz = mod(tree[i << 1].plz * mlz0 + plz0);
    tree[i << 1 | 1].sum = mod(tree[i << 1 | 1].sum * mlz0 + plz0 * (tree[i << 1 | 1].r - tree[i << 1 | 1].l + 1));
    tree[i << 1 | 1].mlz = mod(tree[i << 1 | 1].mlz * mlz0);
    tree[i << 1 | 1].plz = mod(tree[i << 1 | 1].plz * mlz0 + plz0);
    tree[i].mlz = 1, tree[i].plz = 0;
}
inline void add1(ll i, ll l, ll r, ll k) {
    if (tree[i].l >= l && tree[i].r <= r) {
        tree[i].sum = mod(tree[i].sum * k);
        tree[i].mlz = mod(tree[i].mlz * k);
        tree[i].plz = mod(tree[i].plz * k);
        return;
    }
    pushdown(i);
    if (tree[i << 1].r >= l) 
        add1(i << 1, l, r, k);
    if (tree[i << 1 | 1].l <= r)
        add1(i << 1 | 1, l, r, k);
    tree[i].sum = mod(tree[i << 1].sum + tree[i << 1 | 1].sum);
}
inline void add2(ll i, ll l, ll r, ll k) {
    if (tree[i].l >= l && tree[i].r <= r) {
        tree[i].sum = mod(tree[i].sum + k * (tree[i].r - tree[i].l + 1));
        tree[i].plz = mod(tree[i].plz + k);
        return;
    }
    pushdown(i);
    if (tree[i << 1].r >= l) 
        add2(i << 1, l, r, k);
    if (tree[i << 1 | 1].l <= r)
        add2(i << 1 | 1, l, r, k);
    tree[i].sum = mod(tree[i << 1].sum + tree[i << 1 | 1].sum);
}
inline ll search(ll i, ll l, ll r) {
    if (tree[i].l >= l && tree[i].r <= r) 
        return tree[i].sum;
    pushdown(i);
    ll ans = 0;
    if (tree[i << 1].r >= l) 
        ans = mod(ans + search(i << 1, l, r));
    if (tree[i << 1 | 1].l <= r)
        ans = mod(ans + search(i << 1 | 1, l, r));
    return ans;
}
int main() {
    cin >> n >> q >> m;
    for (ll i = 1; i <= n; i++) 
        cin >> a[i];
    build(1, 1, n);
    while (q--) {
        ll op, x, y, k;
        cin >> op;
        if (op == 1) {
            cin >> x >> y >> k;
            add1(1, x, y, k);
        }
        else if (op == 2) {
            cin >> x >> y >> k;
            add2(1, x, y, k);
        } else {
            cin >> x >> y;
            cout << search(1, x, y) << endl;
        }
    }
    return 0;
}

* 补充：快读快写

模板如下：

template<typename T>inline void read(T &x) {
    bool f = 1;x = 0;char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = !f;ch = getchar(); }
    while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    x = (f ? x : -x);return;
}
template<typename T>inline void write(T x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');return;
}

快写不如printf和优化过的cout快，所以还是建议使用prinf。

4 End

参考文章：

  • 线段树 从入门到进阶（超清晰，简单易懂）_进阶线段树-CSDN博客

  • 线段树_百度百科

感谢yes_NT和Happy_WA_Day同学的指导。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/901416.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

PHP-FPM 性能配置优化

PHP-FPM 性能配置优化

4 核 8 G 服务器大约可以开启 500 个 PHP-FPM&#xff0c;极限吞吐量在 580 qps &#xff08;Query Per Second 每秒查询数&#xff09;左右。 Nginx php-fpm 是怎么工作的&#xff1f; php-fpm 全称是 PHP FastCGI Process Manager 的简称&#xff0c;从名字可得知&#xff…
阅读更多...
基于SSM的冰淇淋在线购买网站【附源码】

基于SSM的冰淇淋在线购买网站【附源码】

基于SSM的冰淇淋在线购买网站 效果如下&#xff1a; 系统首页界面 用户登录界面 冰淇淋页面 每日秒杀页面 个人中心界面 管理员登录界面 管理员功能界面 口味管理界面 冰淇淋管理界面 每日秒杀管理界面 视频教学管理界面 研究背景 近些年&#xff0c;随着中国经济发展&#…
阅读更多...
订购 Claude AI 的第二天 它独自完成 文字转语音 flask应用

订购 Claude AI 的第二天 它独自完成 文字转语音 flask应用

图二里&#xff0c;删除几个无关的 chats 全程我做的工作&#xff1a;向 AI 提要求&#xff0c;copy / paste 代码&#xff0c;在venv验证运行&#xff0c;向 AI 反馈&#xff0c;总共用了3个 chats.&#xff08;图中的只有一个 Chat&#xff0c; 删掉的另外两个: Python 库安…
阅读更多...
海外云手机实现高效的海外社交媒体营销

海外云手机实现高效的海外社交媒体营销

随着全球化的深入发展&#xff0c;越来越多的中国企业走向国际市场&#xff0c;尤其是B2B外贸企业&#xff0c;海外社交媒体营销已成为其扩大市场的重要手段。在复杂多变的海外市场环境中&#xff0c;如何有效提高营销效率并降低运营风险&#xff0c;成为了众多企业的首要任务。…
阅读更多...
计算机网络（十二） —— 高级IO

计算机网络（十二） —— 高级IO

#1024程序员节 | 征文# 目录 一&#xff0c;预备 1.1 重新理解IO 1.2 五种IO模型 1.3 非阻塞IO 二&#xff0c;select 2.1 关于select 2.2 select接口参数解释 2.3 timeval结构体和fd_set类型 2.4 socket就绪条件 2.5 select基本工作流程 2.6 简单select的服务器代…
阅读更多...
【mysql进阶】4-8 临时表空间

【mysql进阶】4-8 临时表空间

临时表空间 - Temporary Tablespaces 1 什么是临时表&#xff1f; ✅ 解答问题 临时表存储的是临时数据&#xff0c;不能永久的存储数据&#xff0c;⼀般在复杂的查询或计算过程中⽤来存储过渡的中间结果&#xff0c;MySQL在执⾏查询与计算的过程中会⾃动⽣成临时表&#xff0c…
阅读更多...
C++ 抛异常

C++ 抛异常

目录 一.抛异常与运行崩溃的区别 1.运行崩溃 2.抛异常 二.抛异常机制存在的意义 1.清晰的处理错误 2.结构化的错误管理 3.跨函数传递错误信息 4.异常对象多态性 三.抛异常的使用方法 1.抛出异常 (throw) 2.捕获异常 (catch) 3.标准异常类 四.抛异常的处理机制 1.抛…
阅读更多...
2024“源鲁杯“高校网络安全技能大赛-Misc-WP

2024“源鲁杯“高校网络安全技能大赛-Misc-WP

Round 1 hide_png 题目给了一张图片&#xff0c;flag就在图片上&#xff0c;不过不太明显&#xff0c;写个python脚本处理一下 from PIL import Image ​ # 打开图像并转换为RGB模式 img Image.open("./attachments.png").convert("RGB") ​ # 获取图像…
阅读更多...
rabbitmq 使用注意事项

rabbitmq 使用注意事项

1&#xff0c;注意开启的端口号&#xff0c;一共四个端口号&#xff0c;1883是mqtt连接的端口号&#xff0c;如果没开&#xff0c;是连接不上的需要手动起mqtt插件。 //开始mqtt插件服务 rabbitmq-plugins enable rabbitmq_mqtt 2&#xff0c;15672端口是http网页登录的管理后…
阅读更多...
Next Stack技术联盟成立：打造新一代基础软件技术栈

Next Stack技术联盟成立：打造新一代基础软件技术栈

北京&#xff0c;2024 年 10 月 —— 在全球数字化浪潮的推动下&#xff0c;中国基础软件产业迎来了前所未有的创新机遇与挑战。为应对这一时代任务并推动中国基础软件的全球化进程&#xff0c;观测云携手多家领先技术企业正式宣布成立 Next Stack 技术联盟。这一联盟旨在汇聚国…
阅读更多...
接口测试（五）jmeter——get请求

接口测试（五）jmeter——get请求

一、get请求——短信验证码&#xff08;示例仅供参考&#xff09; 1. get请求&#xff1a;传参数据直接拼接在地址后面&#xff0c;jmeter不需要设置请求头content-type 注&#xff1a;短信验证码接口&#xff0c;返回结果中不会返回短信验证码&#xff0c;是存在数据库表中&a…
阅读更多...
Maven项目管理工具-初始+环境配置

Maven项目管理工具-初始+环境配置

1. Maven的概念 1.1. 什么是Maven Maven是跨平台的项目管理工具。主要服务于基于Java平台的项目构建&#xff0c;依赖管理和项目信息管理。 理想的项目构建&#xff1a;高度自动化&#xff0c;跨平台&#xff0c;可重用的组件&#xff0c;标准化的流程 maven能够自动下载依…
阅读更多...
Mybatis-plus-入门

Mybatis-plus-入门

Mybatis-plus-入门 1&#xff1a;介绍 mybatis-plus的官网&#xff1a;MyBatis-Plus &#x1f680; 为简化开发而生 2: 快速入门 步骤&#xff1a; 1&#xff1a;引入依赖&#xff1a; <dependency><groupId>com.baomidou</groupId><artifactId>my…
阅读更多...
STM32使用硬件I2C读写AT24C02 EEPROM（一）

STM32使用硬件I2C读写AT24C02 EEPROM（一）

文章目录 一、软件准备配置I2C接口&#xff1a;生成工程代码&#xff1a; 二、编写驱动程序初始化I2C接口&#xff1a;编写读写函数&#xff1a; 三、调试与测试 前面讲到使用软件模拟i2c读写AT24C02&#xff0c;这篇文章使用stm32 提供的硬件i2c读写&#xff0c;看看怎么回事 …
阅读更多...
gin入门教程（3）：创建第一个 HTTP 服务器

gin入门教程（3）：创建第一个 HTTP 服务器

首先设置golang github代理&#xff0c;可解决拉取git包的时候&#xff0c;无法拉取的问题&#xff1a; export GOPROXYhttps://goproxy.io再查看自己的go版本&#xff1a; go version我这里的版本是&#xff1a;go1.23.2 linux/arm64 准备工作做好之后就可以进行开发了 3.…
阅读更多...
【AscendC算子开发】笔记1 算子开发哲学

【AscendC算子开发】笔记1 算子开发哲学

重看这门课&#xff0c;有很多内容的认识更深了&#xff0c;做一些记录。 为什么不能将网络节点融合 这个问题关联到另一个问题&#xff1a;为什么我们需要激活函数&#xff1f; 使用线性的神经元堆叠得到的方程最后也是线性方程&#xff0c;无法表征非线性的信息&#xff0c…
阅读更多...
软考（网工）——网络安全

软考（网工）——网络安全

文章目录 &#x1f550;网络安全基础1️⃣网络安全威胁类型2️⃣网络攻击类型 &#x1f551;现代加密技术1️⃣私钥密码/对称密码体制2️⃣对称加密算法总结3️⃣公钥密码/非对称密码4️⃣混合密码5️⃣国产加密算法 - SM 系列6️⃣认证7️⃣基于公钥的认证 &#x1f552;Hash …
阅读更多...
Node.js：深入探秘 CommonJS 模块化的奥秘

Node.js：深入探秘 CommonJS 模块化的奥秘

在Node.js出现之前&#xff0c;服务端JavaScript基本上处于一片荒芜的境况&#xff0c;而当时也没有出现ES6的模块化规范。因此&#xff0c;Node.js采用了当时比较先进的一种模块化规范来实现服务端JavaScript的模块化机制&#xff0c;它就是CommonJS&#xff0c;有时也简称为C…
阅读更多...
react18中使用redux管理公共数据仓库实现数据immutable更新

react18中使用redux管理公共数据仓库实现数据immutable更新

Immutable.js出自Facebook&#xff0c;是最流行的不可变数据结构的实现之一。它实现了完全的持久化数据结构&#xff0c;使用结构共享。所有的更新操作都会返回新的值&#xff0c;但是在内部结构是共享的&#xff0c;来减少内存占用。Immutablejs官网 在上一篇介绍redux的文章&…
阅读更多...
数字IC后端实现 | Innovus各个阶段常用命令汇总

数字IC后端实现 | Innovus各个阶段常用命令汇总

应各位读者要求&#xff0c;小编最近按照Innovus流程顺序整理出数字IC后端项目中常用的命令汇总。限于篇幅&#xff0c;这次只更新到powerplan阶段。有了这份Innovus常用命令汇总&#xff0c;学习数字IC后端从此不再迷路&#xff01;如果大家觉得这个专题还不错&#xff0c;想继…
阅读更多...
最新文章

Copyright @ 2022~2023