线段树主要在区间(长度或索引)固定时,进行区间修改和查询、最值、求和等操作(一般这种操作为O(logn));
平衡树主要在元素集合为动态的情况下,可频繁增删、维护顺序,查询数值x的排名(输出最小的排名)、查询排名为x的数值、求数值x的前驱后继(一般操作为O(logn));
1、线段树(以下模板实现:将某区间每一个数乘上 x;将某区间每一个数加上 x;求出某区间每一个数的和。)
`const int MAXNUM = 1e5 + 10;
int sum[MAXNUM << 2], add[MAXNUM << 2], mul[MAXNUM << 2];//add和mul记录懒标记,sum记录这个区间的区间和
int mod;
void push_up(int rt) {
sum[rt] = (sum[rt << 1] + sum[rt << 1 | 1]) % mod;//将某个点的sum迭代更新为左右儿子的值
}
void push_down(int rt, int m) {
int ls = rt << 1, rs = rt << 1 | 1;
if (mul[rt] != 1) {mul[ls] = (mul[ls] * mul[rt]) % mod;mul[rs] = (mul[rs] * mul[rt]) % mod;add[ls] = (add[ls] * mul[rt]) % mod;add[rs] = (add[rs] * mul[rt]) % mod;sum[ls] = (sum[ls] * mul[rt]) % mod;sum[rs] = (sum[rs] * mul[rt]) % mod;mul[rt] = 1;
}if (add[rt]) {add[ls] = (add[ls] + add[rt]) % mod;//注意这里不是赋值,因为儿子本人可能也有懒标记add[rs] = (add[rs] + add[rt]) % mod;sum[ls] = (sum[ls] + (m - (m >> 1)) * add[rt]) % mod;sum[rs] = (sum[rs] + (m >> 1) * add[rt]) % mod;add[rt] = 0;
}
}
void buildtree(int l, int r, int rt) {
//rt表示当前所使用的树的节点序号,根节点是1号,两个儿子是2、3号,依次往下
add[rt] = 0;
mul[rt] = 1;
if (l == r) {
cin >> sum[rt];
sum[rt] %= mod;
return;
}
int mid = (l + r) >> 1;
buildtree(l, mid, rt << 1);
buildtree(mid + 1, r, rt << 1 | 1);
push_up(rt);//下面的儿孙们都迭代更新完了,现在把rt本人更新一下,更新的素材是两儿子
}
void qjgx(int a, int b, int c, int l, int r, int rt) {
if (a <= l && b >= r) {
sum[rt] = (sum[rt] + (r - l + 1) * c) % mod;
add[rt] = (add[rt] + c) % mod;
return;
}
push_down(rt, r - l + 1);//如果进入到这个迭代轮回中就代表着这段区间要被破坏修改,所以这一段区间的懒标记要被取消、归到儿子们的懒标记中
int mid = (l + r) >> 1;
if (a <= mid) qjgx(a, b, c, l, mid, rt << 1);
if (b > mid) qjgx(a, b, c, mid + 1, r, rt << 1 | 1);//**注意这里一定不可以用else if,否则右儿子会被跳过
push_up(rt);//老规矩更新本人
}
void qjcf(int a, int b, int c, int l, int r, int rt) {
if (a <= l && b >= r) {
sum[rt] = (sum[rt] * c) % mod;
mul[rt] = (mul[rt] * c) % mod;
add[rt] = (add[rt] * c) % mod;//注意乘法会影响加法的内容,因为我在传递的时候是先乘法后加法的,所以加法要加的内容一定也要提前处理成乘过后的‘加数’
return;
}
push_down(rt, r - l + 1);
int mid = (l + r) >> 1;
if (a <= mid) qjcf(a, b, c, l, mid, rt << 1);
if (b > mid) qjcf(a, b, c, mid + 1, r, rt << 1 | 1);
push_up(rt);
}
int qjqh(int a, int b, int l, int r, int rt) {
if (a <= l && b >= r) return sum[rt] % mod;
push_down(rt, r - l + 1);
int mid = (l + r) >> 1;
int ans = 0;
if (a <= mid) ans = (ans + qjqh(a, b, l, mid, rt << 1)) % mod;
if (b > mid) ans = (ans + qjqh(a, b, mid + 1, r, rt << 1 | 1)) % mod;
return ans % mod;
}
signed main() {
int n, q;
cin >> n >> q >> mod;
buildtree(1, n, 1);//建树
while (q--) {
int op, x, y, k;
cin >> op;
if (op == 1) {
cin >> x >> y >> k;
qjcf(x, y, k, 1, n, 1);
} else if (op == 2) {
cin >> x >> y >> k;
qjgx(x, y, k, 1, n, 1);
} else {
cin >> x >> y;
cout << qjqh(x, y, 1, n, 1) % mod << endl;
}
}
return 0;
}`
线段树的功用类似于前缀和
2、平衡树Treap(维护动态集合)
`const int N = 100010, INF = 1e8;
int n;
struct Node
{
int l, r;
int key, val;
int cnt, size;
}tr[N];
int root, idx;
void pushup(int p)
{
tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + tr[p].cnt;
}
int get_node(int key)
{
tr[ ++ idx].key = key;
tr[idx].val = rand();
tr[idx].cnt = tr[idx].size = 1;
return idx;
}
void zig(int &p) // 右旋
{
int q = tr[p].l;
tr[p].l = tr[q].r, tr[q].r = p, p = q;
pushup(tr[p].r), pushup(p);
}
void zag(int &p) // 左旋
{
int q = tr[p].r;
tr[p].r = tr[q].l, tr[q].l = p, p = q;
pushup(tr[p].l), pushup(p);
}
void build()
{
get_node(-INF), get_node(INF);
root = 1, tr[1].r = 2;
pushup(root);
if (tr[1].val < tr[2].val) zag(root);
}
void insert(int &p, int key)
{
if (!p) p = get_node(key);
else if (tr[p].key == key) tr[p].cnt ++ ;
else if (tr[p].key > key)
{
insert(tr[p].l, key);
if (tr[tr[p].l].val > tr[p].val) zig(p);
}
else
{
insert(tr[p].r, key);
if (tr[tr[p].r].val > tr[p].val) zag(p);
}
pushup(p);
}
void remove(int &p, int key)
{
if (!p) return;
if (tr[p].key == key)
{
if (tr[p].cnt > 1) tr[p].cnt -- ;
else if (tr[p].l || tr[p].r)
{
if (!tr[p].r || tr[tr[p].l].val > tr[tr[p].r].val)
{
zig(p);
remove(tr[p].r, key);
}
else
{
zag(p);
remove(tr[p].l, key);
}
}
else p = 0;
}
else if (tr[p].key > key) remove(tr[p].l, key);
else remove(tr[p].r, key);
pushup(p);
}
int get_rank_by_key(int p, int key) // 通过数值找排名
{
if (!p) return 0;
if (tr[p].key == key) return tr[tr[p].l].size + 1;
if (tr[p].key > key) return get_rank_by_key(tr[p].l, key);
return tr[tr[p].l].size + tr[p].cnt + get_rank_by_key(tr[p].r, key);
}
int get_key_by_rank(int p, int rank) // 通过排名找数值
{
if (!p) return INF;
if (tr[tr[p].l].size >= rank) return get_key_by_rank(tr[p].l, rank);
if (tr[tr[p].l].size + tr[p].cnt >= rank) return tr[p].key;
return get_key_by_rank(tr[p].r, rank - tr[tr[p].l].size - tr[p].cnt);
}
int get_prev(int p, int key) // 找到严格小于key的最大数
{
if (!p) return -INF;
if (tr[p].key >= key) return get_prev(tr[p].l, key);
return max(tr[p].key, get_prev(tr[p].r, key));
}
int get_next(int p, int key) // 找到严格大于key的最小数
{
if (!p) return INF;
if (tr[p].key <= key) return get_next(tr[p].r, key);
return min(tr[p].key, get_next(tr[p].l, key));
}
int main()
{
build();
scanf("%d", &n);
while (n -- ){
int opt, x;
scanf("%d%d", &opt, &x);
if (opt == 1) insert(root, x);
else if (opt == 2) remove(root, x);
else if (opt == 3) printf("%d\n", get_rank_by_key(root, x) - 1);
else if (opt == 4) printf("%d\n", get_key_by_rank(root, x + 1));
else if (opt == 5) printf("%d\n", get_prev(root, x));
else printf("%d\n", get_next(root, x));
}
return 0;
}`