权值sgt

id: sgt_weights

线段树题目 AHOI2009 维护序列 与例题3差不多 洛谷P1253 扶苏的问题 稍微复杂的懒标记维护 洛谷P5142 区间方差 需要一定的数学推导能力 P4145 花神游历各国 想一想如何优化？ P1471 方差 3题的加强版，较难 P6327 区间加区间sin和 需要一些高中的数学知识

作用:

前提:动态修改的添加向数组里添加一个数a,a∈[1,n]a \in [1,n],其中[1,n]称为数字的值域

区间桶

权值线段树就是另一个角度来看sgt,sgt代码的本质没有改变.

特点:基本上在值域[1,1e5]上,也就是离散化后最多有1e5个不同的值

  • 求带修改的整体第k大
  • 排名
  • 前趋
  • 后继
  • 求逆序数: 原理和bit一样,求出第i数工[]
  • 出现最多的数
  • 总和最大的数

a[i] ,<= a[i]数量,大于a[i]的数量i-a[i]

  • loj 10116 TODO pcs查看

  • 洛谷P3369 提供几道权值线段树的习题。

  1. loj10114.数星星 Stars 权值线段树，需要用动态开点或离散化的优化
  2. P1168 中位数 离散化，然后开权值线段树维护
  3. P2073 送花 可以用权值线段树做
  4. SDOI2014 旅行 树链剖分（如果你会的话），用动态开点维护

参考