数据结构-平衡树-Treap

定义 “维护一个有序数列,有插入、删除、查询第k大、查询前驱、后继等操作”,对于这种问题,我们常用到二叉排序树(BST,Binary Sort Tree,也称二叉查找树、二叉搜索树)这种数据结构,而Treap就是对它的一种优化

Continue reading

数据结构-ST表

定义 范围最值查询问题(Range Minimum Query,RMQ):给定一个数组\(A[1\ldots n]\),询问若干次:指定\(i\)和\(j\),计算\(min\{A[i],A[i+1],\ldots ,A[r]\}\)或\(max\{A[i],A[i+1],\ldots ,A[r]\}\)。 ST表是解决RMQ问题的一种数据结构。

Continue reading