acwing算法提高之数据结构--线段树

目录

  • 1 介绍
  • 2 训练
  • 3 参考

1 介绍

线段树是算法竞赛中常用的用来维护区间信息的数据结构。

线段树可以在O(logN)时间复杂度内完成以下操作：

  1. 单点修改。
  2. 区间修改（需要加入懒标记）。
  3. 区间查询（区间求和、求区间最大值、求区间最小值）。

2 训练

题目1：1275最大数

C++代码如下，
涉及到单点修改、区间查询最大值这两个操作。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 2000010;

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 * 2].v, tr[u * 2 + 1].v);
}

void build(int u, int l, int r) { //建立线段树
    tr[u] = {l, r};
    if (l == r) return;
    int mid = l + r >> 1;
    build(2 * u, l, mid), build(2 * u + 1, mid + 1, r);
}

int query(int u, int l, int r) {//查询区间[l,r]最大值
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].v; 
    int mid = tr[u].l + tr[u].r >> 1;
    int v = 0;
    if (l <= mid) v = query(2 * u, l, r);
    if (r > mid) v = max(v, query(2 * u + 1, l, r));
    return v;
}

void modify(int u, int x, int v) { //单点修改:将a[x]修改为v,线段树tr[u]需要进行的操作
    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(2 * u, x, v);
        else modify(2 * u + 1, x, v);
        pushup(u);
    }
}

int main() {
    int n = 0, last = 0;
    cin >> m >> p;
    build(1, 1, m);
    
    int x;
    string op;
    while (m--) {
        cin >> op >> x;
        if (op == "Q") {
            last = query(1, n - x + 1, n);
            cout << last << endl;
        } else {
            modify(1, n + 1, ((LL)last + x) % p);
            n++;
        }
    }
    return 0;
}

题目2：245你能回答这些问题吗

C++代码如下，
涉及到单点修改、求区间的最大连续子数组和这两个操作。

#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);
    }
}

void 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;
}

题目3：246区间最大公约数

C++代码如下，

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 500010;

int n, m;
LL w[N];
struct Node {
    int l, r;
    LL sum, d;
}tr[N * 4];

LL gcd(LL a, LL b) {
    return b ? gcd(b, a % b) : a;
}

void pushup(Node &u, Node &l, Node &r) {
    u.sum = l.sum + r.sum;
    u.d = gcd(l.d, r.d);
} 

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) {
        LL b = w[r] - w[r-1];
        tr[u] = {l, r, b, b};
    } else {
        tr[u].l = l, tr[u].r = r;
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int x, LL v) {
    if (tr[u].l == x && tr[u].r == x) {
        LL b = tr[u].sum + v;
        tr[u] = {x, x, b, b};
    } 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("%lld", &w[i]);
    build(1, 1, n);
    
    int l, r;
    LL d;
    char op[2];
    while (m--) {
        scanf("%s%d%d", op, &l, &r);
        if (*op == 'Q') {
            auto left = query(1, 1, l);
            Node right({0, 0, 0, 0});
            if (l + 1 <= r) right = query(1, l + 1, r);
            printf("%lld\n", abs(gcd(left.sum, right.d)));
        } else {
            scanf("%lld", &d);
            modify(1, l, d);
            if (r + 1 <= n) modify(1, r + 1, -d);
        }
    }
    return 0;
}

题目4：243一个简单的整数问题2

C++代码如下，

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n, m;
int w[N];
struct Node {
    int l, r;
    LL sum, add;
}tr[N * 4];

void pushup(int u) {
    tr[u].sum = tr[u<<1].sum + tr[u<<1|1].sum;
}

void pushdown(int u) {
    auto &root = tr[u], &left = tr[u<<1], &right = tr[u<<1|1];
    if (root.add) {
        left.add += root.add, left.sum += (LL)(left.r - left.l + 1) * root.add;
        right.add += root.add, right.sum += (LL)(right.r - right.l + 1) * root.add;
        root.add = 0;
    }
}

void build(int u, int l, int r) {
    if (l == r) tr[u] = {l, r, w[r], 0};
    else {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u<<1, l, mid), build(u<<1|1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int l, int r, int d) {
    if (tr[u].l >= l && tr[u].r <= r) {
        tr[u].sum += (LL)(tr[u].r - tr[u].l + 1) * d;
        tr[u].add += d;
    } else {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u<<1, l, r, d);
        if (r > mid) modify(u<<1|1, l, r, d);
        pushup(u);
    }
}

LL query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
    
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    LL sum = 0;
    if (l <= mid) sum = query(u<<1, l, r);
    if (r > mid) sum += query(u<<1|1, l, r);
    return sum;
}

int main() {
    scanf("%d%d", &n, &m);
    
    for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);
    
    build(1, 1, n);
    
    char op[2];
    int l, r, d;
    
    while (m--) {
        scanf("%s%d%d", op, &l, &r);
        if (*op == 'C') {
            scanf("%d", &d);
            modify(1, l, r, d);
        } else printf("%lld\n", query(1, l, r));
    }
    
    return 0;
}

题目5：247亚特兰蒂斯

C++代码如下，

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 100010;

int n;
struct Segment {
    double x, y1, y2;
    int k;
    bool operator< (const Segment &t) const {
        return x < t.x;
    }
}seg[N * 2];

struct Node {
    int l, r;
    int cnt;
    double len;
}tr[N * 8];

vector<double> ys;

int find(double y) {
    return lower_bound(ys.begin(), ys.end(), y) - ys.begin();
}

void pushup(int u) {
    if (tr[u].cnt) tr[u].len = ys[tr[u].r + 1] - ys[tr[u].l];
    else if (tr[u].l != tr[u].r) {
        tr[u].len = tr[u<<1].len + tr[u<<1|1].len;
    }else tr[u].len = 0;
}

void build(int u, int l, int r) {
    tr[u] = {l, r, 0, 0};
    if (l != r) {
        int mid = l + r >> 1;
        build(u<<1, l, mid), build(u<<1|1, mid+1, r);
    }
}

void modify(int u, int l, int r, int k) {
    if (tr[u].l >= l && tr[u].r <= r) {
        tr[u].cnt += k;
        pushup(u);
    } else {
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u<<1, l, r, k);
        if (r > mid) modify(u<<1|1, l, r, k);
        pushup(u);
    }
}

int main() {
    int T = 1;
    while (scanf("%d", &n), n) {
        ys.clear();
        for (int i = 0, j = 0; i < n; ++i) {
            double x1, y1, x2, y2;
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            seg[j++] = {x1, y1, y2, 1};
            seg[j++] = {x2, y1, y2, -1};
            ys.push_back(y1), ys.push_back(y2);
        }
        
        sort(ys.begin(), ys.end());
        ys.erase(unique(ys.begin(), ys.end()), ys.end());
        
        build(1, 0, ys.size() - 2);
        
        sort(seg, seg + n * 2);
        
        double res = 0;
        for (int i = 0; i < n * 2; ++i) {
            if (i > 0) res += tr[1].len * (seg[i].x - seg[i-1].x);
            modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].k);
        }
        
        printf("Test case #%d\n", T++);
        printf("Total explored area: %.2lf\n\n", res);
    }
    
    return 0;
}

题目6：1277维护序列

C++代码如下，

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n, p, m;
int w[N];
struct Node {
    int l, r;
    int sum, add, mul;
}tr[N * 4];

void pushup(int u) {
    tr[u].sum = (tr[u<<1].sum + tr[u<<1|1].sum) % p;
}

void eval(Node &t, int add, int mul) {
    t.sum = ((LL)t.sum * mul + (LL)(t.r - t.l + 1) * add) % p;
    t.mul = (LL)t.mul * mul % p;
    t.add = ((LL)t.add * mul + add) % p;
}

void pushdown(int u) {
    eval(tr[u<<1], tr[u].add, tr[u].mul);
    eval(tr[u<<1|1], tr[u].add, tr[u].mul);
    tr[u].add = 0, tr[u].mul = 1;
}

void build(int u, int l, int r) {
    if (l == r) tr[u] = {l, r, w[r], 0, 1};
    else {
        tr[u] = {l, r, 0, 0, 1};
        int mid = l + r >> 1;
        build(u<<1, l, mid), build(u<<1|1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int l, int r, int add, int mul) {
    if (tr[u].l >= l && tr[u].r <= r) eval(tr[u], add, mul);
    else {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u<<1, l, r, add, mul);
        if (r > mid) modify(u<<1|1, l, r, add, mul);
        pushup(u);
    }
}

int query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
    
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    int sum = 0;
    if (l <= mid) sum = query(u<<1, l, r);
    if (r > mid) sum = (sum + query(u<<1|1, l, r)) % p;
    return sum;
}

int main() {
    scanf("%d%d", &n, &p);
    for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);
    build(1, 1, n);
    
    scanf("%d", &m);
    
    while (m--) {
        int t, l, r, d;
        scanf("%d%d%d", &t, &l, &r);
        if (t == 1) {
            scanf("%d", &d);
            modify(1, l, r, 0, d);
        } else if (t == 2) {
            scanf("%d", &d);
            modify(1, l, r, d, 1);
        } else printf("%d\n", query(1, l, r));
    }
    return 0;
}

3 参考

线段树 - OI Wiki

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

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

相关文章

2024/5/4 英语每日一段

2024/5/4 英语每日一段

But something is slowing that rocket down: lack of access to the types of data used to train robots so they can interact more smoothly with the physical world.It’s far harder to come by than the data used to train the most advanced AI models like GPT—mos…
阅读更多...
08 IRF技术 华三交换机实现

08 IRF技术 华三交换机实现

IRF 详细介绍 我知道 AI IRF 技术是指集成路由功能（Integrated Routing and Bridging）技术，是惠普（Hewlett Packard）公司开发的一种基于硬件的虚拟化技术。IRF 技术可以将多台物理设备组合成一个逻辑设备，实现设备的高可用性和灵活性。 IRF 技术主要有以下特点： 1. …
阅读更多...
Linux---为什么会有粘滞位？

Linux---为什么会有粘滞位？

在前面已经讲过目录的rwx权限&#xff1a; 可读权限(r): 如果目录没有可读权限, 则无法用ls等命令查看目录中的文件内容. 有可写权限(w):如果目录没有可写权限&#xff0c;则无法在目录中创建文件, 也无法在目录中删除文件.可执行权限(x): 如果目录没有可执行权限, 则无法cd到…
阅读更多...
五一后返工，3招帮你快速找回状态！

五一后返工，3招帮你快速找回状态！

五一假期即将结束&#xff0c;如何快速进入工作状态 随着五一假期的临近结束&#xff0c;我们即将迎来新的工作挑战。在享受了短暂的休息和放松之后&#xff0c;重新调整心态&#xff0c;迅速进入工作状态显得尤为重要。本文将为您提供一些实用的方法和建议&#xff0c;帮助您…
阅读更多...
Elasticsearch中【文档查询】DSL语句以及对应的Java实现

Elasticsearch中【文档查询】DSL语句以及对应的Java实现

目录 全文检索查询 精准查询 布尔查询 排序、分页查询 高亮 地理查询 复合查询 Elasticsearch提供了基于JSON的DSL&#xff08;Domain Specific Language&#xff09;来定义查询。常见的查询类型包括&#xff1a; 查询所有&#xff1a;查询出所有数据&#xff0c;一般测…
阅读更多...
【业务场景】京东实际场景，频繁GC引起的CPU飙高问题的解决

【业务场景】京东实际场景，频繁GC引起的CPU飙高问题的解决

目录 1.业务介绍 2.判断任务类型 3.CPU飙高的原因 1.业务介绍 本文的业务场景是京东零售线公开的一篇文章&#xff0c;文章内容详细介绍了京东零售线如何将广告相关的定时任务从半小时优化到秒级的&#xff0c;原文链接&#xff1a; 半小时到秒级&#xff0c;京东零售定时…
阅读更多...
BUUCTF：Web 解析（一）

BUUCTF：Web 解析（一）

前言 Buuctf Web 是一个在线安全挑战平台&#xff0c;旨在提高参与者对网络安全的理解和实践能力。本文将详细介绍 Buuctf Web 的特点、挑战和机遇&#xff0c;帮助读者更好地了解这一领域。 一、Buuctf Web 的特点 多样化的挑战场景&#xff1a;Buuctf Web 提供了多种挑战场…
阅读更多...
Redis事务,管道,发布订阅

Redis事务,管道,发布订阅

Redis事务 redis事务本质上是一组命令的集合,按照顺序串行化执行命令而不被其他命令打断 redis事务开启后将要执行的命令放到事务队列中,提交事务后一次性顺序排他地执行所有命令 关键词:单线程,无隔离级别,不保证原子性,排他性,顺序性 要注意和mysql的acid进行区分 怎么用…
阅读更多...
【JavaEE】多线程安全问题

【JavaEE】多线程安全问题

文章目录 1、什么是多线程安全问题2、出现线程不安全的原因2.1 线程在系统中是随机调度&#xff0c;抢占式执行的2.2 多个线程同时修改同一个变量2.3 线程针对变量的修改操作&#xff0c;不是“原子”的2.4 内存可见性问题2.5 指令重排序 3 、如何解决线程安全问题3.1 锁操作3.…
阅读更多...
2024年3月Scratch图形化编程等级考试（三级）真题试卷

2024年3月Scratch图形化编程等级考试（三级）真题试卷

2024年3月Scratch图形化编程等级考试&#xff08;三级&#xff09;真题试卷 选择题 第 1 题 Scratch运行程序后&#xff0c;角色一定不会说出的数字是&#xff1f;&#xff08; &#xff09; A.2 B.4 C.6 D.8 第 2 题 Scratch角色初始位置如下图所示&#xff0c;右图…
阅读更多...
14_Scala面向对象编程_属性

14_Scala面向对象编程_属性

属性 1.类中属性声明 // 1.给Scala声明属性&#xff1b;var name :String "zhangsan"val age :Int 302.系统默认赋值 scala由于初始化变量必须赋值&#xff0c;为了解决此问题可以采用下划线赋值&#xff0c;表示系统默认赋值 , –但是此方法局限于变量&…
阅读更多...
ArkTS开发原生鸿蒙HarmonyOS短视频应用

ArkTS开发原生鸿蒙HarmonyOS短视频应用

HarmonyOS实战课程“2024鸿蒙零基础快速实战-仿抖音App开发&#xff08;ArkTS版&#xff09;”已经于今日上线至慕课网&#xff08;https://coding.imooc.com/class/843.html&#xff09;&#xff0c;有致力于鸿蒙生态开发的同学们可以关注一下。 课程简介 本课程以原生鸿蒙Ha…
阅读更多...
Hibernate执行流程分析及配置文详解

Hibernate执行流程分析及配置文详解

目录 1、Hibernate执行流程分析及配置文件详解 1&#xff09;Configuration对象 2&#xff09;ServiceRegistry对象&#xff08;hibernate4的新特性&#xff09; 3&#xff09;SessionFactory对象 4&#xff09;Session对象 5&#xff09;Transaction对象 6&#xff09;…
阅读更多...
缓冲流，BufferReader,BufferWriter,案例

缓冲流，BufferReader,BufferWriter,案例

IO流的体系 字节缓冲流的作用 提高字节流读取数据的性能 *原理&#xff1a;字节缓冲输入流自带了8Kb的缓冲池&#xff0c;字节缓冲输出流也自带了8kb的缓冲池 构造器说明public BufferedInputStream(InputStream is)把低级的字节输入流包装成一个高级的缓冲字节输入流&#…
阅读更多...
对链表进行插入排序（详细解析）

对链表进行插入排序（详细解析）

对链表进行插入排序&#xff08;详解&#xff09; 题目&#xff1a; 对链表进行插入排序 给定单个链表的头 head &#xff0c;使用 插入排序 对链表进行排序&#xff0c;并返回 排序后链表的头 。 插入排序 算法的步骤: 插入排序是迭代的&#xff0c;每次只移动一个元素&a…
阅读更多...
特斯拉FSD落地分析

特斯拉FSD落地分析

再续前缘 媒体的神经从马斯克的湾流私人飞机起飞那一刻开始，就开始被牵动着。28/4 号的突然访华，在大多数人看来其实已经早已是计划之中，从摆在台面上的消息来看，主要目的是为了在大陆推广FSD的落地，也为8月份FSD 的正式版本做预热，和中国上海的第一次联姻造就了特斯拉m…
阅读更多...
17 内核开发-内核内部内联汇编学习

17 内核开发-内核内部内联汇编学习

​ 17 内核开发-内核内部内联汇编学习 课程简介&#xff1a; Linux内核开发入门是一门旨在帮助学习者从最基本的知识开始学习Linux内核开发的入门课程。该课程旨在为对Linux内核开发感兴趣的初学者提供一个扎实的基础&#xff0c;让他们能够理解和参与到Linux内核的开发过程中…
阅读更多...
【Linux】进程exec函数族以及守护进程

【Linux】进程exec函数族以及守护进程

一.exec函数族 1.exec函数族的应用 在shell下敲shell的命令都是在创建shell的子进程。而我们之前学的创建父进程和子进程代码内容以及通过pid与0的关系来让父子进程执行不同的代码内容都是在一个代码文件里面&#xff0c;而shell是如何做到不在一个文件里面写代码使之成为子进…
阅读更多...
06｜LangChain | 从入门到实战 -六大组件之Agent

06｜LangChain | 从入门到实战 -六大组件之Agent

点点赞~ 注意&#xff1a;langchain的版本迭代比较快&#xff0c;社区维护&#xff0c;代码当中或许部分方法在某个版本不再支持 01&#xff5c;LangChain | 从入门到实战-介绍 02&#xff5c;LangChain | 从入门到实战 -六大组件之Models IO 03&#xff5c;LangChain | 从入…
阅读更多...
asp.net结课作业中遇到的问题解决2

asp.net结课作业中遇到的问题解决2

目录 1、如何实现评论交流的界面 2、如果想要将文字添加到数据库中&#xff0c;而不是乱码&#xff0c;该怎么修改 3、如果想要添加的数据已经存在于数据库&#xff0c;就不允许添加了&#xff0c;该如何实现 4、想要实现某个模块下有好几个小的功能该如何实现 5、想要实现…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站