st表、树状数组与线段树 笔记与思路整理 |
您所在的位置：网站首页 › 区间树和线段树区别 › st表、树状数组与线段树 笔记与思路整理 |
st表、树状数组与线段树 笔记与思路整理
|
已更新（2/3）：st表、树状数组
st表、树状数组与线段树是三种比较高级的数据结构，大多数操作时间复杂度为O(log n)，用来处理一些RMQ问题或类似的数列区间处理问题。 一、ST表（Sparse Table） st表预处理时间复杂度O(n log n)，查询O(1)，但不支持在线更改，否则要重新进行预处理。 使用一个二维数组：st[i][j]存储i为起点，长度为2j的一段区间最值，即arr[i, i + 2j - 1]。 具体步骤（以最小值为例）： 将st[i][0]赋值为arr[i]; 利用动态规划思想，dp出st[i][j] = min(st[i][j - 1], st[i + 2j - 1][j - 1]) (1 ≤ i ≤ n, 1 ≤ j ≤ log2 n)； 查询时，定义len为log2(r - l + 1)，区间[l, r]的最小值为min(st[l][len],st[r - 2len + 1][len])。总时间复杂度为O(n log n + q)，q为请求数。 代码实现（两个st表分别求最大最小值）：  
#include
using namespace std;
int stmin[60010][20], stmax[60010][20];
int n, q, arr[60010], minans, maxans;
void init(){
for(int j = 1 ; j > n >> m;
int opt, pos, l, r, num;
for(int i=1; i> n >> m;
char opt;
int pos, l, r, num;
for(int i=1; i> a[i];
add_node(i, a[i] - a[i-1]);
}
while(m--){
cin >> opt;
if(opt == 'C'){
cin >> l >> r >> num;
add_range(l, r, num);
}
if(opt == 'Q'){
cin >> l >> r;
cout |
【本文地址】