统计的力量.ppt

1、清华大学，张，一体化联系统计，2020年7月19日，清华大学，张，2。许多算法的本质是统计。根据克努特的分类方法，计算机算法可分为两类：数值算法和非数值算法，其中非数值算法包括：指数分类统计，2020年7月19日，清华大学，张，3，线段树？每个人都说：常数很大？难写吗？难以调试？出乎意料？2020年7月19日，张，清华大学4号，一出悲剧，出了问题，时间限制很紧，大家都用树阵，但有些人只用行树？此外，我可以很容易地纠正一个我不能使用树数组的问题。在一次又一次的线段树的TLE之后，有一个标识发帖抱怨“下次写一个非递归线段树的汇编版本，然后超时？”但是我们都知道，超时代码是2k。实际上，我写了一个线

2、形树。很快，不到一千。2020年7月19日，张，清华大学，5。线段树用于统计，运行速度快，适应性强，结构简单，调试容易。关键在于灵活的实施。线段树来自哪里？为什么在算法和黑皮书的介绍中很难看到它的踪迹？2020年7月19日，清华大学张，2020年6月19日，清华大学张，7日，计算几何！在计算几何的长期发展中，许多实用的数据结构已经诞生。区间查询和穿孔查询都是计算几何解决的问题。作为一种特殊情况，线段树解决的问题是：一维空间中的几何统计量被扩展到高维空间(KD-树/成为开区间s=M，t=M；/在不(s xor t)=1)的情况下找到叶子位置，如果(s和1)=0)答案=树1，则执行此操作；如果(t

3、和1)=1)，答案=树1；s=s 1，t=t1；2020年7月19日，清华大学张，31岁，C语言比较简单！对于(s=s M-1，t=t M-1；st1S=1，t=1)如果(s，2020年7月19日，张，清华大学，32，警告，当将封闭区间转换为开放区间时，它可能出界。事实上，树只能查询0，2N-2的范围。记不记得，2020年7月19日，张魏坤，清华大学33号，否如果需要查询间隔在1023年0月底1024？慢点。你的数据不是1000吗？如果真的达到1023，那么直接将总间隔改为0，2048是非常残忍的。2020年7月19日，张，清华大学，34，修改更简单，Funct Change(n，NewVaL

4、ue)n=M；Treen=新值；当n=n时，n=ntreen=tree 2n tree 2n 1；2020年7月19日，张，清华大学，35岁，C语言比较简单，为(Tn=M=V，n=1；n；n=1)Tn=Tn n Tn n 1；走了吗？它不见了。2020年7月19日，清华大学张，36岁，技术参数？仅使用原始阵列的两倍空间，这也完全包括原始阵列：的简单构造，对于I=m-1向下到1 do ti=t2i t2i1写起来太容易了！善解人意！从下到上，它只被访问一次，不一定被访问到顶层。它在实践中速度非常快，并且接近树阵列。为什么？我们以后再谈。2020年7月19日，张，清华大学37岁，人家的树阵只使用了

5、两倍的空间，因为树阵依赖于区间减法和区间减法，我讨厌以后再谈它。无论如何，如果我只要求前缀和，如果我不要求间隔和，我只能使用两倍的空间！2020年7月19日，清华大学张，38岁，自然非递归方法！2020年7月19日，清华大学张，39岁，自然非递归方法！2020年7月19日，清华大学张，40岁，自然非递归方法！2020年7月19日，清华大学41岁的张，他所有的儿子都没用了。2020年7月19日，清华大学42岁的张节约了一半空间。这不是和树形数组一样吗？应该是一样的。回头看看，什么是树型阵列？也就是说，线段树在节省一半空间和中间顺序遍历后需要低位来计算位置。我们使用一阶遍历，这符合人们的思维习惯。

6、然而，没有必要节省这个空间。它需要一点空间来实现绝对的简单。2020年7月19日，张，清华大学，43岁，哈哈，2020年7月19日，张，清华大学，44岁，只是为了好玩，我以前用这种方式做过很多题。每个人都说我的代码不能理解我。我说这是一个树形数组。写树形数组的人说没有低位。我说它是一棵线树。你不会相信非递归线树这么短。I:标志的传递。2020年7月19日，张，清华大学，45岁，区间修改，噩梦开始，2020年7月19日，张，清华大学，46岁，2020年7月19日，张，清华大学，47岁，用区间修改，(Range Minor Query)区间最小查询线段树支持区间修改：2020年7月19日，清华大学

7、的张，48岁，42岁，在线段树中的每个节点都添加了一个标记，以指示这个区间已经增加了多少如果您在自顶向下的递归过程中看到该标记，请更新当前节点的值并下载该标记。又从上到下？2020年7月19日，张，清华大学，49，马克永久。事实上，堆存储也可以从上到下访问，也就是说，它只上下移动一次，但是我们有一个更好的方法(仔细想想，你就会知道)。在自底向上的查询过程中，当您进入每个级别时，使用它而不是下载标记是合理的。我们愿意在树的根部存储尽可能多的信息，那么我们通过下载标签做什么呢？常数很小：一次通过，永久标记是值，庄，2020年7月19日，张，清华大学，50，张，清华大学，51，着色问题，线段，支持区

8、间着色。询问间隔是相同的颜色吗？间隔染色需要使用染色标记1表示红色，2表示蓝色，3表示绿色，0表示杂色。直接看分数2020年7月19日清华大学52岁的张。2是红色，3是蓝色，1是噪音，3是红色，查询1是噪音？永久标志是一种价值！该值会自动维护！事实上，我们的修改算法在修改3时保持了1。重新计算自下而上遇到的所有节点标记，即如果(标记x=0，标记2x=标记2x1)标记x=标记2x；2020年7月19日，清华大学53岁的张，狗叼走了老鼠，猫被解雇了。回到区间修正的RMQ，通俗地说，这个标记是一个相对量。既然有标记，值有什么用？或者，如果值本身是相对的，您需要标记它吗？如果我让所有的数字都从零开始变

9、化，所有的值在标记永久化后都将是零！所以我们甚至没有价值。持久标记是一个值。2020年7月19日，清华大学54岁的张，你是什么意思？每个节点不存储间隔Tn的最大值，而是存储Mn=Tn-Tn1，因此每个节点的值从其父亲的值间隔中减去，然后直接改变Mn。查询从要查询的节点开始，一直持续到根节点。TN=Mn Mn1 M1；满足节点x，则a=min (m2x，m2x1) MX=a，m2x-=a，m2x1-=a，2020年7月19日，清华大学张，55，简单，函数add _ x (s，t，x)为(s=s m-1，t st1S=1，t=1)如果(s，2020年7月19日，清华大学张，56，太简单，太，fun

10、cmax (s，t)为(s=s m-1，t=t m-1；st1s=1，t=1) LAns=Ts，Rans=Tt如果(S，2020年7月19日，张，清华大学，57，开悟，差异是把绝对变成相对的重要手段，并且在标记永久性之后，它是一个值，但是在计算答案时，可以用从节点到根的信息，2020年7月19日，张，清华大学，58，替代，作为PPT的生产，大部分每个人使用的线段树都是从上到下在线段树中从上到下。标记通常不是永久性的。对RMQ来说，有必要下载标记。对于染色问题，有必要下载和收集标记想法，这与我这里的方法类似。实施上的差异是从上到下至少一次访问，但速度很慢。参见其他材料。2020年7月19日，清华

11、大学59岁的张仍有一笔债务。线段树是连接原始数组和前缀和的桥梁。桥的两端同时进行差分前缀和差分逆运算。因此，线段树也是连接差异和原始数组的桥梁。如果要支持区间修改，单点查询不需要使用标签，原始数组差的前缀和可以直接由线段树维护。其实，现在还能说什么呢，2020年7月19日，清华大学张，60岁，前缀加前缀加？在没有标签帮助的情况下，区间修改和区间求和(原始)被支持首先被区分，然后成为维持前缀和的前缀和。前缀和的前缀和是多少？SS1=S1=X1SS2=S1=2x1x 2s 3=S1S 2 S3=3 x12x2x 3=4(1x 2x 3)-(1x 12x 3x 3)只需再保留一个前缀和nxn。数学，

12、数学！2020年7月19日，张，清华大学，61，最长上升间隔列，最长上升“间隔列”，找出间隔列中的最大间隔，以便它们不重叠并单调增加为1，3 2，4 4，5。答案是1，3，4，5。动态规划的可行决策是什么？如果要使升序列的长度大于x，那么最后一个数字的最小值是多少，这叫做fx维护fx支持点查询和区间修改。2020年7月19日，张，清华大学，62，前缀min的逆运算，点查询：查询fx在X处的取值范围，修改：X左边所有超过K的值都变成K，改变X的左右两边()整个f-x是单调递减的，单调递减的序列可以视为前缀min得到的公共序列！前缀min的逆运算是什么？我们不在乎。2020年7月19日，清华大学6

13、3岁的张，这样可以吗？我们现在需要维护的是前缀min逆运算后的原始序列！但是我们甚至不知道前缀min的逆运算是什么。没关系，反正我们也不需要。点击查询：查询x处的fx值，直接返回维护序列的前缀最小间隔。修改：x左侧所有超过k的值都变成k，维护序列中的f x变成k，线段树，太灵活了！张，2020年7月19日，清华大学，64岁，但不要迷信线树，不要迷恋哥哥，哥哥只是一个传说，张，2020年7月19日，清华大学，65岁，张，清华大学，66岁，重要条件：区间加法，说这么多，可以用线树解决问题。也就是说，区间的“性质”完全由子区间决定，包括但不限于求和、寻求最大值和寻求染色状态。这里的“自然”有点像动态

14、编程的状态。有时候，寻求更多更容易。最简单的例子：如果间隔的第二个最大值真的不满足间隔加法，那么它将全部完成。2020年7月19日，清华大学67岁的张难道没有遇到区间加法？我们都知道，在线段树中找到区间的平均值并不难。什么，不难吗？然后要求另一种模式？2020年7月19日，张，清华大学68岁，不满足区间加法！它变得越来越难的原因很简单。如果你知道两个区间的中间值，你就会知道和区间的中间值。了解它们各自的模式有什么用？2020年7月19日，咋要求更多越来越容易。线段树的每个部分必须保留更多信息！所有区间数的有序数组存储在每个区间中，通过合并完成区间加法。2020年7月19日，张70岁的清华大学分

15、校，合并非常缓慢。如果每次进行查询时都合并几个线段，那么离散化的复杂度将达到O(n)！二元答案！它变成：间隔的最大数量是多少？这可以通过分别在两个部分中搜索几个线段来获得。总复杂度O(nlogn Q*log2n)，另一种原始方法，将在后面讨论，2020年7月19日，清华大学张，71，区间减法，如果有区间减法的线树，它甚至可以更强大，如“区间和”就变成“前缀和”，这要简单得多，也是使用树数组的一个条件，但这不是必须的(与区间加法比较)我说我以后再谈，2020年7月19日，清华大学张，2020年7月19日，清华大学张维护数据结构并支持整数插入。最大整数范围是065535。2020年7月19日，清华

16、大学74岁的张老师的大动作，堆积如山没关系，但的黑皮书却有大动作！“分段哈希”分为几个部分。保存“该段中有编号吗？”的信息2020年7月19日，清华大学张，75岁，分段哈希，2020年7月19日，清华大学张，76岁。多层怎么样？三楼？四楼？直到每个节点下只有两个点！我们得到了什么，2020年7月19日，清华大学张，77岁，这也是一棵线树，2020年7月19日，清华大学张，78岁，哈哈，平衡树vs线树，不要折腾，2020年7月19日，清华大学张，79岁，2020年7月19日，清华大学张维护一个数据结构，支持整数插入和整数删除，取第k个最大的数(不要提最大和最小的一个)，查询这个数的排名， 检查某个数字是否允许元素重复(为了方便起见)，整数范围为065535，2020年7月19日，清华大学张，81，统计幂！ 平衡树？线形树！统计数字0，65536)每个数字的出现频率被记录为fx整数插入、fx整数删除、fx -查询数字排序、寻找前缀并取第k个最大的数字(更不用说最大和最小的数字)，给出前缀和，从上到下搜索，如果左边不够则向右，否则向左。2020年7月19日，张，清华大学82岁，事半功倍。人们发现线段树可以很快地处理这类问题。平衡树中最快的大小平衡树用了4秒钟，线段树