学习线段树，你需要先完成树、数组、分治思想、递归的学习（可以说是学习成本极低了） 引入 线段树是一个用途极为广泛的数据结构，在提高组及以上的比赛中经常看到它的身影。 现在我有一个问题，给一个长度为 $n$ 的序列，我需要将序列中一个范围内的每一个数进行一次运算，例如加上 $x$ ，也就是区间修改，然后查询修改后一个区间范围内所有值的和或者其他量，也…

主席树，又叫可持久化权值线段树，也叫函数式线段树，是可持久化线段树的子集。在本文中，我们可以认为主席树等于可持久化线段树 可持久化线段树简介 基本结构、特点、作用在这篇文章中已经提到过：线段树扩展：权值线段树 总的来说就是每次修改或插入一个值，就新建一个根节点，并且向下递归去新建其他节点。 优点解释 每次插入操作最多创建的节点数都为$\log n$…

传送门 题目强调与分析 翻译本题：给出一串长度为 $n$ 的字符串，其中只包含 "$B$" ， "$R$" 两种字符，分别表示蓝色和红色，每一个字符还附有一个值，对于每次操作，你可以选择其中一个字符，对它的值进行以下两种修改： 如果颜色是红色，可以通过一次操作将它的值 $+1$ ；如果颜色是蓝色，可以通过一次操作将它的值 $-1$ ； 求：是否存在…

前言 先前博客中写过“线段树”这一篇文章，而这一次是一种具有新的含义的线段树：权值线段树。 权值线段树简介 定义 权值线段树和普通线段树的形态类似，但是含义不同。普通线段树的节点通常存储该区间的最值或者和值，其节点范围是一个区间：权值线段树的节点存储该值域内的元素个数，其节点范围是一个值域。 基本结构 如图，对于每个节点的位置表示的是元素的值，然后…

学习扫描线，你需要先学习线段树和离散化 扫描线简介 扫描线是一种求矩形面积并/周长的好方法，同样的，它可以延伸到很多地方。注意，扫描线并不是一条存在的线，是在解释算法时的帮助我们更好理解的线。 扫描线原理 现在在平面直角坐标系中有$n$个矩形，它们相互重叠在一起，求出所有矩形占有的面积（重叠部分只算一次）。如果采用暴力枚举每一个点，那么空间与时间都…

线段树简介 主要作用： 线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。 时间复杂度： 每一次查询、修改：$$ O(log N) $$ 基本形态： 若用 $ tree[ ] $ 表示树， $ x $ 表示线段树上的节点， $ tree[x] $ 表示节点所表示的…