事情是这样的，当我用zrem命令去移除value的时候，我知道他之前会做的几个步骤1、查找这个value对应的score（通过zset中的dict）2、根据这个score查找到跳表中的节点3、删除这个节点我就想了一下为什么dict为什么要保存score呢？如果保存的是跳表中的节点，那么不就可以做到删除O(1)

1.定义在点分治的基础上加以变化，构造一颗支持快速修改的重构树，称之为点分树2.算法2.1.思路点分治的核心在于通过树的重心来划分联通块，减少合并层数，从而降低时间复杂度所以，我们可以按分治递归的顺序提出一颗树，易知树高至多为logn具体的说，对于每一个找到的重心，将上一次分治

2024.4.11【虚怀若谷，戒骄戒躁。】Thursday三月初三<theme=oi-"language">这个好东西叫pb_ds!!!#include<bits/extc++.h>usingnamespace__gnu_cxx;usingnamespace__gnu_pbds;堆操作/数据结构配对堆二叉堆左偏树二项堆斐波那契堆代码pairing_heap_t

空间复杂度原因是因为需要额外数组空间来进行排序时间复杂度T(n)=2T(n/2)+O(n),a=2,b=2,c=1根据master公式可知时间复杂度O(nlogN)归并排序可以排序数据量很大的数组,举例说明,例如要排序有2^64个数字的数组,那么归并排序将会开辟64层系统栈,这并不会导致栈溢出.include<stdio

在之前的文章《最小熵原理（六）：词向量的维度应该怎么选择？》中，我们基于最小熵思想推导出了一个词向量维度公式“n>8.33logN�>8.33log⁡�”，然后在《让人惊叹的Johnson-Lindenstrauss引理：应用篇》中我们进一步指出，该结果与JL引理所给出的O(logN)�(log⁡�)是吻合的。既然理论上看上去很完美，

给出一个长度为nn的数组，完成以下两种操作：1.将第ii个数加上kk2.输出区间[i,j][i,j]内每个数的和朴素算法单点修改：O(1)O(1)区间查询：O(n)O(n)使用树状数组单点修改：O(logn)O(logn)区间查询：O(logn)O(logn)前置知识lowbit()lowbit()运算：非负整数xx在二进制表示下最低位1及其后面的0构

这是一道模板题首先，对任意时刻，\(u\)->\(v\)这条路径上的点都是不会变动的（就是说，比如，如果某时刻从\(1\)到\(4\)的路径为\(1\)->\(3\)->\(4\)，那么对之后的任意时刻，这条路径都是这个，既不会改变顺序，也不会新增节点，更不会删除已有节点），所以我们可以把所有有效的操作一存起来最后再建边

今天在看到O（logn）的时候，先去看了下什么是对数，有一个博主说的特别好，经过勤奋的工作之后，已经忘记了什么是对数。参考百度百科的对数公式：对数公式是数学中的一种常见公式，如果ax=N(a>0,且a≠1)，则x叫做以a为底N的对数,记做x=logaN，其中a要写于log右下。其中a叫做对数的底，N叫做真数。通

递归的本质是系统帮我们进行了压栈，栈的名字叫做系统栈。但系统栈的空间十分有限，因此在工程上我们需要把递归改写成用内存中的栈来模拟系统压栈，以此来实现非递归。master公式又叫主定理，是一种估算递归时间复杂度的公式。但有个前提条件:只有是子问题规模相同的递归才能使用。T(N)

树状数组所维护的数组记为\(a\)，\(n\)表示\(a\)中元素个数，\(lowbit(i)\)表示最低位\(1\)和后面所有\(0\)组成的数，\(c[i]\)表示\(a\)区间\([i-lowbit(i)+1,i]\)的和。\(add(k,x)\)：单点修改，表示\(a[k]=a[k]+x\)，时间复杂度：\(O(logn)\)。\(sum\)：区间查询，\(sum(k)\)表示\(a\)区

红黑树(RedBlackTree)红黑树性质null节点只是一种记号，并不存储真实数据，也不是红黑树中的实际节点，其作用是方便程序员在设计和编程时理解节点的操作规则，在实际应用中并没有实际意义。红黑树的等价变换红黑树和4阶B树(2-3-4树)具有等价性红黑树是平衡二叉搜索树，而B树是

排序算法哪些是稳定的排序算法，哪些是不稳定的稳定的：直接插入排序：最坏情况是逆序，时间复杂度是O(N2)，最好情况是插入的都是顺序，时间复杂度O(N)，空间复杂度O(1)冒泡排序：时间复杂度O(N2)，空间复杂度O(1)计数排序：时间复杂度O(N+Range)，空间复杂度O(range)不稳定：希尔排序：时间复杂度O(N

排序算法哪些是稳定的排序算法，哪些是不稳定的稳定的：直接插入排序：最坏情况是逆序，时间复杂度是O(N^2^)，最好情况是插入的都是顺序，时间复杂度O(N)，空间复杂度O(1)冒泡排序：时间复杂度O(N^2^)，空间复杂度O(1)计数排序：时间复杂度O(N+Range)，空间复杂度O(range)不稳定：希尔排序：时间复杂

总结：数据库存储顺序随机，如果没有索引，每次查询都需要一行行遍历，查找出符合条件的点，复杂度O(N)数据库会按照rowid排序，并给主键建立索引，所以如果以rowid或者主键为搜索条件，复杂度可以近似看做二分查找的复杂度，即O(logN)如果没有主键，或搜索条件不是主键，可以给搜索目标增加索

排序总结时间复杂度空间复杂度是否能有稳定性选择O(N*N)O(1)×冒泡O(N*N)O(1)✔️插入O(N*N)O(1)✔️归并O(N*logN)O(N)✔️快排(一般指3.0)O(N*logN)O(N*logN)×堆O(N*logN)O(1)×基数排序作为不基于比较的排序，有稳定性基础类型的排序一般排序用快排，因为其时间复杂度常数项更小，需要保持

树状数组用于变化区间的动态维护进行\(O(logn)\)的插入和删除。\(lowbit(x)\)表示二进制表示中最低位的1代表的值称为最小位值，实际上就是二进制表示中最低位的1代表的值称为最小位值二进制表示中最低位的1加上后面的0的值。设树状数组\(c\)，\(c_i\)表示${\textstyle\sum

排序算法的时间复杂度和空间复杂度最好时间复杂度最坏时间复杂度平均时间复杂度空间复杂度是否为稳定排序是否为原地排序冒泡排序$O(n)$初始数组正序$O(n^2)$初始数组逆序$O(n^2)$$O(1)$原地使用数组，无额外内存开销是是插入排序是是选择排序$O(n

元素入队时间复杂度O(logn)，查询O(1)，总体排序时间复杂度O(logn)，用于优化一些大数据范围的排序，具体用法如下：#include<bits/stdc++.h>usingnamespacestd;priority_queue<int,vector<int>,less<int>>q;//less<int>：和greater<int>相反structnode{inti,v;};pr

mid=(L+R)/2可能会溢出；改成mid=L+(L-R)/2；提升效率，改成mid=L+(R-L)>>1。mid=(L+R)/2可能会溢出；改成mid=L+(L-R)/2；提升效率，改成mid=L+(R-L)>>1。其中：a代表子规模执行次数，b代表子规模大小，d代表除了子规模调用其他的操作的时间复杂度。若logba<d，时间复杂度为O(Nd)

递归行为的时间复杂度估算整个递归过程是一棵多叉树，递归过程相当于利用栈做了一次后序遍历。对于master公式，T(N)表明母问题的规模为N，T(N/b)表明每次子问题的规模，a为调用次数，加号后面表明，除去调用之外，剩余语句的复杂度是多少，算出d。根据上次三个判断公式进行算法时间复杂度计算

查找性能为O(logn)。从最上层开始查找，找到小于目标的最大节点。插入性能高于平衡树。插入一个元素时，会为该元素生成随机个索引层。跳表使用简单的随机数操作而构建出来的多层链表结构，就获取查找性能为O(logn)【论文中有数学证明】

跳表和红黑树查找的时间复杂度都是logN，插入删除也是logN。范围查找貌似也都是O(k+logn)，其中n是树中节点的数量，k是满足范围条件的节点数量。但是实现起来跳表要简单很多。1.zset有个很核心的操作叫范围查找，我们要查找某个范围区间的元素。跳表可以做到logN时间复杂度内的快

1.引入先给出一个问题给出样例：方法1：看到这个问题，我的第一个想法是按题意根据每一个询问暴力找出区间最大值，但很明显这是会超时的。方法2：当然也有快一点的方法，可以先预处理，将所有可能的区间最大值全求出来，然后再询问时输出。具体的话就是先把每相邻两个的最大值求出来，然

ST表学习笔记与总结目录ST表定义/作用什么是可重复贡献问题ST算法流程模板提ST表定义/作用什么是可重复贡献问题ST算法流程模板提luoguP3865【模板】ST表我的代码#include<iostream>usingnamespacestd;constintN=1e5+10,logN=21;intn,

概念https://zhuanlan.zhihu.com/p/92920381树状数组（BinaryIndexedTree,又FenwickTree）其实并不是一棵树，只是对数组各元素进行逻辑上的划分。根据维基百科，树状数组是一种用于高效计算数列前缀和的数据结构，它可以以O(logn)的时间得到任意前缀和（两个前缀和相减即可得到区间和），并