首页 > 其他分享 >数据结构——线段树 学习笔记

数据结构——线段树 学习笔记

时间:2024-03-12 09:48:44浏览次数:26  
标签:int 线段 mid 笔记 build push 数据结构 void

数据结构——线段树 学习笔记

class seg_t {

private:

struct emm {
    int l, r;
    struct v;
};

vector<emm> a;

void push_up(int k) { }
void action(int k, int v) { }
void push_down(int k) { }

void build(vector<any> q, int k, int l, int r) {
    a[k].l = l, a[k].r = r;
    if (l == r) { return; }
    int mid = l + (r - l >> 1);
    build(q, k * 2, l, mid);
    build(q, k * 2 + 1, mid + 1, r);
    push_up(k);
}

void modify(int k, int p, int q, int v) {
    auto &l = a[k].l, &r = a[k].r;
    if (l >= p && r <= q) return void(action(k, v));
    int mid = l + (r - l >> 1);
    if (mid >= p)     modify(k * 2, p, q, v);
    if (mid + 1 <= q) modify(k * 2 + 1, p, q, v);
    push_up(k);
}

int query(int k, int p, int q) {
    auto &l = a[k].l, &r = a[k].r;
    int mid = l + (r - l >> 1);
    int res;
    if (mid >= p)     res += query(k * 2, p, q);
    if (mid + 1 <= q) res += query(k * 2 + 1, p, q);
    return res;
}

public:

};

然后参考:https://www.cnblogs.com/RainPPR/p/18066950/scanning

以及:https://www.cnblogs.com/RainPPR/p/17974548/segment-tree-2

没了。是不是很水?

标签:int,线段,mid,笔记,build,push,数据结构,void
From: https://www.cnblogs.com/RainPPR/p/18067623/segment-tree

相关文章

  • 技术笔记(7)Unity导入人物和场景,出现的材质问题
    技术笔记(7)Unity导入人物和场景,出现的材质问题一,如果两个人物拥有同名但内容不同的的材质shadererror:Unity在导入的时候,识别到近似内容时,会用新的内容去替换同名shader的内容,而不是重新创建一个。这样就会导致第一个人物的材质显示异常,其本质是shader内容被替换了。解决......
  • BUUCTF靶机笔记
    BUUBRUTE11启动靶机后可以看到是一个登陆页面查看源代码:没有有用的信息只是单纯的html页面随便填一个用户:admin密码:123提示密码为四位怀疑是暴力破解使用burp进行单点爆破payload设定暴力完成查看length不同的数据包返回flag:flag{6982d5b6-a2f8-48d8-aec6......
  • 线段树(C++)
    线段树的本质就是树状数组,只不过线段树不再需要lowbit函数来定位对应数据的存储位置,取而代之的则是直接计算分叉结果位置。node结构体​ 通常而言,线段树所需要的存储空间约等于原数组的4倍。由于线段树需要存储区间的范围,所以我们需要自己定义一个新结构体来方便存储:constint......
  • (C++)树状数组和线段树的VSCode Snippet
    学都学了,肯定要往snippet里塞好东西嘛{ //Placeyoursnippetsforcpphere.Eachsnippetisdefinedunderasnippetnameandhasaprefix,bodyand //description.Theprefixiswhatisusedtotriggerthesnippetandthebodywillbeexpandedandinserted.......
  • 博弈论个人笔记总结
    博弈论简单易懂的博弈论讲解(巴什博弈、尼姆博弈、威佐夫博弈、斐波那契博弈、SG定理)-The_Virtuoso-博客园(cnblogs.com)尼姆博弈(Nim)游戏引入:假设先手为$X$,后手为$Y$先假设有两堆石子,数量分别为a,b,如果$a\neqb\and\a>b$,$X$选石子$x$个让$a-x=b$,然后$......
  • Minitorch笔记
    https://github.com/mukobi/Minitorch-Self-Study-Guide-SAIA/blob/main/README.md#what-is-thishttps://minitorch.github.io/srush/GPU-Puzzles:Solvepuzzles.LearnCUDA.(github.com)代码规范和提交black.#Formatallfilesflake8.#checkdocstringandetc.my......
  • vue3—尚硅谷禹神笔记转载
    1.Vue3简介2020年9月18日,Vue.js发布版3.0版本,代号:OnePiece(n经历了:4800+次提交、40+个RFC、600+次PR、300+贡献者官方发版地址:Releasev3.0.0OnePiece·vuejs/core截止2023年10月,最新的公开版本为:3.3.41.1.【性能的提升】打包大小减少41%。初次渲染快5......
  • GraphDA论文阅读笔记
    Abstract​ 图协同滤波(GCF)是在推荐系统中捕获高阶协同信号的一种流行技术。然而,GCF的二部邻接矩阵定义了基于用户-项目交互聚合的邻居,对于交互丰富的用户/项目来说是有噪声的,而对于交互稀缺的用户/项目则不够。此外,邻接矩阵忽略了用户-用户和项目-项目之间的相关性,这可能会限制被......
  • 计算几何——扫描线 学习笔记
    计算几何——扫描线学习笔记你会发现我的笔记的顺序和很多扫描线的讲解是反着来的。其实是和我老师给的课件完全是逆序(谁帮我算一下逆序对啊喵)。前言一开始以为扫描线就是用来求二维几何图像的信息的。但是其实这个并不准确。个人认为,扫描线其实是一个思想,就像动态规划一样......
  • Java学习笔记——第十二天
    面向对象高级(三)内部类内部类是类中的五大成分之一(成员变量、方法、构造器、内部类、代码块),如果一个类定义在另一个类的内部,这个类就是内部类。场景:当一个类的内部,包含了一个完整的事物,且这个事物没有必要单独设计时,就可以把这个事物设计成内部类。比如:汽车类中的发动机类,发动......