当前位置: 首页 > news >正文

线段树与平衡树

线段树主要在区间(长度或索引)固定时,进行区间修改和查询、最值、求和等操作(一般这种操作为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;
}`

http://www.hskmm.com/?act=detail&tid=32300

相关文章:

  • 面向对象进阶-2
  • CF2155 Codeforces Round 1056 (Div. 2) 游记(VP)
  • 【隐语SecretFlow社区】万字长文解读构建可信数据空间相关标准
  • Android四大组件之Servers、BroadcastReceiver、ContentProvider(内容提供者)
  • 2025年智能装备与机器人国际学术会议(IER 2025)
  • 编程计算定投黄金的收益率
  • 客户管理软件是什么?深度解析及标杆产品推荐
  • openresty开发lua-resty-openssl之rsa公钥加密私钥解密 - liuxm
  • 2025年6款主流CRM系统详解
  • 动手动脑及实验性问题总结
  • 华为云rds pg 11升级17
  • 盘点2025破碎仪厂家/提供研磨处理方案的厂家
  • 全球顶尖的医疗器械CRM软件(深度对比)
  • uni-app x开发商城系统,tabBar
  • Delphi TscGPPageControl动态创建新页面与加载Frame框架
  • 静态方法访问类的实例成员
  • 2025年冷冻研磨仪厂家,研磨仪厂家排行,知名品牌介绍
  • 组织研磨仪厂家品牌推荐/知名品牌,组织研磨仪哪家好?
  • The World of Torrents (How it Works?)
  • 进口微量粘度计代理商推荐,优质供应商分享
  • 10月16日
  • 进口高温高压粘度计优质供应商,粘度计代理商推荐
  • Apache Doris 内部数据裁剪与过滤机制的完成原理
  • 2025 年循环烘箱厂家推荐榜:热风循环烘箱厂家聚焦节能智能,这家企业成多行业优选
  • 10.16
  • 2598. 执行操作后的最大 MEX——模运算
  • 2025通风天窗厂家推荐正鑫,专业定制工业厂房通风排烟系统
  • 阿里面试:Redis挂了怎么办?集群 节点挂,怎么 恢复数据? 多长时间 的数据 可能 丢失?
  • Ubuntu 上安装 PHP 环境
  • 2025年工业陶瓷厂家 TOP 企业品牌推荐排行榜,工业陶瓷,氧化铝陶瓷推荐这十家公司!