_kirito__

线段树

Codeforces(2) Contest(3) STL(1) 二分(2) 前缀和(2) 动态规划(2) 图论(4) 并查集(3) 搜索(3) 操作系统(1) 数位dp(2) 杂项(2) 模拟(1) 题解(1)

/ 注册

全部文章 / 线段树（共5篇）

牛客小白月赛24—I.求和

牛客小白月赛24—I.求和题目描述已知有\(n\)个节点，有\(n-1\)条边，形成一个树的结构。给定一个根节点\(k\)，每个节点都有一个权值，节点\(i\)的权值为\(v_i\)。给\(m\)个操作，操作有两种类型： 1 a x : 表示将节点\(a\)的权值加上x...

2020-04-19

0 454

天才的记忆

天才的记忆题目描述：从前有个人名叫WandNandB，他有着天才般的记忆力，他珍藏了许多许多的宝藏。在他离世之后留给后人一个难题（专门考验记忆力的啊！），如果谁能轻松回答出这个问题，便可以继承他的宝藏。题目是这样的：给你一大串数字（编号为1到N，大小可不一定哦！），在你看过一遍之后，...

2020-03-15

0 627

线段树

线段树概念线段树是一颗二叉树，二叉树的节点保存着区间信息，跟节点表示1-n，左右子节点分别表示左右各半区间，如图：由此可以看出，二叉树最后一层有n个节点，所以二叉树的层数为O（logn）这也使得二叉树的查询效率为O（logn），但是最后一层可能不为满二叉树。应用对于二叉树的适...

2020-02-28

0 429

RMQ

RMQ问题： RMQ问题是Range Maximum Query的缩写顾名思义就是区间最大值问题，对于这类问题的求解方法是——ST算法，ST算法采用一种类似动态规划的求解方式，可以在O(nlogn)内处理，O(1)询问，但是不支持修改，因此适用于极大数据量的查询问题。 ST：对于a[1],a...

2020-02-22

0 386

GCD

GCD：题目描述：给定一个长度为N的数列A，以及M条指令，每条指令可能是以下两种之一： 1、“C l r d”，表示把 A[l],A[l+1],…,A[r] 都加上 d。 2、“Q l r”，表示询问 A[l],A[l+1],…,A[r] 的最大公约数(GCD)。对于每个询问，输出一...

2020-02-21

0 490