[动态开点线段树][学习笔记]

权值线段树

所谓权值线段树,就是指线段树内存的是权值。好像是废话。给出一些数,要查询一个区间内的数的个数。这时可以用权值线段树,开个n(n为给出的数的最大值)个点的线段树。然后就能轻松的维护了当然树状数组更简单

动态开点

为什么要动态开点呢?当然是因为空间不够啊。比如还是上面那个例子。加入给出的数的最大值为\(10^{12}\),并且无法离散化,显然空间开不下。那么就需要动态开点了。

思想

动态开点的思想就是,初始线段树只有一个根。当插入节点的时候在把那些需要的节点开出来。具体方法其实看一下代码就明白了。

void update(int &rt,int l,int r,int pos,int c) {
   if(!rt) {
      rt = ++num;
      tree[rt] = c;
   }
   tree[rt] = min(tree[rt],c);
   if(l == r) return;
   int mid = (l + r) >> 1;
   if(pos <= mid) update(ls[rt],l,mid,pos,c);
   else update(rs[rt],mid + 1,r,pos,c);
}

这就是插入的代码。注意在rt上面是有"&"的。其他的操作就和普通线段树一样了。

一道例题

hdu6183
题解

全部评论

相关推荐

02-23 19:27
门头沟学院 Java
点赞 评论 收藏
分享
01-21 12:26
暨南大学 golang
点赞 评论 收藏
分享
浪子陪都:简历最优秀的地方放到了后面,国奖,校级奖学金这些是最亮眼的。说明你跟同级别的学生不一样。 建议台灯这个,PCB布局布线这个词汇不专业,业内是PCB Layout,第二,单片机的板子一般不用考虑SI,PI 都是低速信号,只要遵循3W原则就好了。 单片机的项目太low了,技能这块,你要看一下BOSS直聘的招聘要求,按照别人的要求写,一些关键词可以增加你简历被检索到的概率。 主修课程不用写,这个没有人去关注的。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务