哈希表

缘起

我们之前学过的N多树来进行排序, 但是基于CBA理论（【1】）这种树的排序算法的性能极限就是O(nlogn). 但是哈希算法并不基于比较，所以他的性能可以到达O(n). 但是代价是较大的空间复杂度. 本文给出哈希表的实现.

归并排序求逆序数牛客网

缘起

【1】中我们已经给出了使用树状数组+离散化来求一个序列的逆序数的O(nlogn)算法. 这里给出使用归并排序的过程中完成逆序数的求解. 题目链接依旧是

离散化树状数组求逆序数

缘起

一个序列的逆序数的定义是所有元素的逆序值之和. 而一个元素的逆序值的定义是

a[1,…,n] 中 a[i]的逆序值是a[i+1,…,n]中比a[i]严格小的元素的个数.

poj 3468 A Simple Problem with Integers 树状数组

缘起

问题: 给你一个数列,每次询问(Q)一个区间的和,或者每次将一个区间的所有元素都加上(A)一个数.数列的项数不超过10万,每个数的范围是正负十亿之间,要处理的询问次数不超过10万条.

疯狂的区间树状数组

缘起

【1】中我们使用树状数组给出了一个点相关的区间个数的求法. 本文将使用树状数组给出区间相关的点的操作.

问题:

给定一个整数序列a, 对a有以下操作

① 修改操作：将A[L..R]之间的全部元素值加上C,记为(L,R,C)；② 询问：求此时A[x]的值。

poj 2481 Cows 树状数组

缘起

树状数组,又叫做Binary Index Tree (BIT) 或者 Fenwick 树.主要用于查询任意两位之间的所有元素之和. 引入树状数组的缘起是为了能高效求数组的片段和.

一般的，一个数组修改一个元素和片段求和的复杂度分别是O(1)和O(N), 但是现在树状数组的引入，以牺牲修改单个元素性能为代价，但是树状数组大大提高了片段求和的性能——树状数组修改单个元素和片段求和的性能都是O(logN).

为了入门树状数组，我们拿 poj 2481 Cows 来练手.

poj 1442 Black Box treap

缘起

【1】给出了treap的板子，自然找一道题来测下板子的性能. 于是选择了 poj 1442

poj 3481 SBT Double Queue

缘起

【1】中讲解了SBT的模板. 这里自然需要用oj检验一下板子的性能. 所以选择了 poj 3481 来练手.

Treap

缘起

接【1】，我们给出oj中常用的另一种平衡树——Treap，

SBT

缘起

关于BST，我们已经介绍很多了. 尤其是针对他的最坏O(N)的弊病, 人们给出了AVL、Splay、红黑树等解决方案. 但是avl和红黑树较为复杂，实际算法竞赛的时候用的不多. 一般用的比较多的是splay、sbt、treap （所谓三大平衡树），这里讲解【1】中介绍的SBT. 它对于平衡的刻画既不是AVL的子树深度，亦不是红黑树的路径上的黑色节点的个数. 而是子树节点个数.