线段树
功能(不带懒标记版本)
- 单点修改
- 区间查询
1 建树过程
建树的依据:一般分为3种
(1). 根据下标进行建树
(2). 原数组元素的值域不大且值域内元素个数有限,根据值域进行建树
(3). 若原数组的值域太大或者为值域内元素个数无限(double类型的值域)。
则需离散化后,按照离散化后的下标作为新的值域,建立树状数组。
2 关于节点数量与数组空间大小的解释:假设区间是[1, n]
建树的过程,我们是不断将区间进行折半拆分的,直至区间大小为1为止。
(1). 单看节点:最后一行最多也就n个节点,而总的 实际会用到的节点数 也就2n左右。
(2). 再看下标:只是我们建树是按照堆的形式建的,所以下标方面要取倒数第二行的数的2倍。
而倒数第二行的节点数量最多可以是n这个级别的,当然一定是严格小于n的
于是最后一行的下标应该是倒数第二行这个节点下标的两倍。
倒数第二行节点下标上限大约是n * 2这个级别,
所以最多需要4 * n的节点空间大小以方便堆形式的访问。
3 几个基本操作函数的参数说明
(1). pushup(int u)综合一个u这个节点的两个儿子信息
(2). build(int u, int l, int r)从u这个节点开始填充每个节点的信息
涉及修改,需pushup
(3). query(int u, int L, int R)从u这个节点开始查询L~R这段区间的信息,递归时L, R不变。
query不涉及修改,故没有pushup
(4). modify(int u, int x, int v)修改左右区间为[x, x]的节点信息,递归时,x, v不变
涉及修改,需pushup
4 易错点
build时,非叶子节点填充l, r信息
query时,写混tr[u]的l,r和查询区间的L,R
注意区间的端点时l ~ mid mid + 1 ~ r
5 区间查询的时间复杂度分析4logn
如图:分类讨论
保证不论那种情况,下一层都会有一个儿子进入L <= Tl && Tr <= R这个不递归的部分
代码
#include<iostream>
using namespace std;
const int N = 200010;
int n, m, p;
struct Node {
int l, r;
int v;
}tr[N * 4];
void pushup(int u) {
tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}
void build(int u, int l, int r) {
tr[u] = {l, r};
if (l == r) return ;
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
}
int query(int u, int l, int r) {
int Tl = tr[u].l, Tr = tr[u].r;
if (l <= Tl && Tr <= r) return tr[u].v;
int mid = Tl + Tr >> 1;
int res = 0; // 注意初始化
if (l <= mid) res = query(u << 1, l, r);
if (r >= mid + 1) res = max(res, query(u << 1 | 1, l, r));
return res;
}
void modify(int u, int x, int v) {
if (tr[u].l == x && tr[u].r == x) {
tr[u].v = v;
} else {
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
pushup(u);
}
}
int main() {
scanf("%d %d", &m, &p);
build(1, 1, m);
int a = 0;
char op[2];
int x;
while (m--) {
scanf("%s %d", op, &x);
if (*op == 'Q') {
a = query(1, n - x + 1, n);
printf("%d\n", a);
} else {
modify(1, ++n, (a + x) % p);
}
}
return 0;
}