• 2022.08.21 吉司机线段树略讲


    Interpretation \color{green}{\texttt{Interpretation}} Interpretation

    吉司机线段树(A.K.A. 势能线段树),个人觉得,就是对普通线段树的一种优化技巧。这种优化技巧有点像搜索算法里面的剪枝。

    在普通线段树中,为了避免一次区间操作浪费太多时间,我们利用了一种叫作懒标记Lazy Tag)的技巧。懒标记的核心是利用操作的可合并性,当进行操作时,先在根节点上进行标记,需要访问子节点时再把标记下放。

    但是,对于一些没有可合并性的操作(比如开平方等),懒标记就不适用了。

    但是,既然题目出出来了,就应该有方法解,这类型的题目的操作大多有一个共同点:操作次数比较有限。

    比如 开平方并向下取整 操作,哪怕是一个很大的数,通过有限次操作( 64 64 64 位正整数好像最多只需要 25 25 25 次吧,不记得了)就可以使它变成 1 1 1,然后操作就失效了(再操作也还是 1 1 1)。

    我们可以想象有这些数本身就有一定的某种“势能”,而每次操作都会使得这个“势能”降低,知道达到最低(即使操作失效)。

    我们可以记录下这个“势能”,然后进行区间修改时,先判断这个区间的最高“势能”是否已经达到了最低,如果是,那么这个操作对于这个区间而言就失效了,可以退出操作。

    如果“势能”下降的速度足够开,就可以使时间复杂度降低到可以承受的范围。

    比如对于那个 开平方并向下取整 的操作来说,我们就记录下每个区间的最大值,如果某个区间的最大值已经是 1 1 1 了,那么进行操作时就可以忽视这个区间。

    Example   -   Hdu   7059 \color{green}{\texttt{Example - Hdu 7059}} Example - Hdu 7059

    [Problem] \color{blue}{\texttt{[Problem]}} [Problem]

    给定长度为 n n n 的数列 a 1.. n a_{1 .. n} a1..n,三种操作:

    1. 求区间和
    2. 将区间内的所有数减去它的 lowbit
    3. 将区间内的所有数加上它的 highbit

    [Analysis] \color{blue}{\texttt{[Analysis]}} [Analysis]

    不是很显然的,我们知道,操作 2 2 2 会使每个数二进制下 1 1 1 的个数减少 1 1 1,而操作 3 3 3 不会影响每个数二进制下 1 1 1 的个数。

    于是可以使用吉司机线段树,“势能”就是每个数二进制下 1 1 1

  • 相关阅读:
    博客系统的页面设计
    C++ gstreamer函数使用总结
    【英语考研词汇训练营】Day 15 —— analyst,general,avoid,surveillance,compared
    罗德里格斯公式
    力扣 53. 最大子数组和(C语言+分治递归、动态规划)
    Vue3——teleport 传送门
    【分布式深度学习】--- 环境构建篇之基于物理机-手把手
    Elasticsearch节点及存储规划建议
    单核CPU如何执行多线程
    流量卡名字不符,为什么流量卡名字和说明书上的不一样吗?
  • 原文地址:https://blog.csdn.net/ZHUYINGYE_123456/article/details/126449970