权值线段树

  线段树的两个拓展：动态开点线段树和权值线段树。  线段树有两种写法：堆形式存储和结点形式存储  通常来说，线段树占用空间是总区间长的常数倍，空间复杂度是 。然而，有时候很巨大，而我们又不需要使用所有的节点，这时便可以动态开点——不再一次性建好树，而是一边修改、查询一边建立。我们不再用堆形式中p
算法 2022年12月08日 459次浏览

算法—线段树

线段树之所以称为“树”，是因为其具有树的结构特性。线段树由于本身是专门用来处理区间问题的。对于每一个子节点而言，都表示整个序列中的一段子区间;对于每个叶子节点而言，都表示序列中的单个元素信息;子节点不断向自己的父亲节点传递信息，而父节点存储的信息则是他的每一个子节点信息的整合。线段树就是分块思想的树
算法 2022年12月06日 383次浏览

算法—扫描线

扫描线一般用于解决面积并的问题，最简单的应用是求矩形的面积并。使用针对不同数据范围可以有两种方式。方式一： 利用区间合并暴力求解，时间复杂度为O(n^2*logn)，可以用于解决数据量为1e3级别的问题。方式二： 利用线段树 + 扫描线，时间复杂度为O(nlogn)，可以用于解决数据量为1e5级别的
算法 2022年12月05日 479次浏览

贪心算法

贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择 。1、微扰(邻项交换)证明在任意局面下，任何对局部最优策略的微小改变都会造成整体结果变差。经常
算法 2022年11月29日 429次浏览

两种离散化方法分析

两种离散化方法分析
算法 2022年11月27日 485次浏览