线段树题目解析

  ① 01 数列区间异或,区间求和

    区间异或其实也不会难,只需要碰到完整的区间时将整个区间的和改成区间长度 - 原区间和,其它类似于上面的题目。

  ② 线段树 + 数学内容

    题意大致如下:

      给定一个长度为 $n$ 的数列 $A_1,A_2,...,A_n$,有 $m$ 种操作,每次操作给出操作区间端点 $l,r$:

        1. 随机打乱下标在 $[l,r]$ 之间的所有数的值;

        2. 求 $sum_{i=l}^r A_i$ 的期望值对 $10^9+7$ 取模。

    解析:

      观察 “打乱” 操作,因为是随机的,所以最后取出的每个数的期望值都是相同的。

      但这串数的和是固定的,所以随机打乱后,每个数的期望值就是原区间的平均数。

      这题求和时有模数,所以处理平均数时可以用逆元。

      然后这题就变成了区间修改、区间求和的模板题。

  ③ 区间开平方(下取整),区间求和(数值在 int 范围内,序列长度、操作次数不超过 $10^5$)

    观察发现,一个 int 的数只需要开方超过 $5$ 次,就一定会变成 $1$。

    所以只需要在线段树中加一个记录区间最大值的标记,如果最大值等于 $1$,就直接返回。

    复杂度 $O(5n ;log ;n)$,可以通过。

原文地址:https://www.cnblogs.com/zengpeichen/p/12331917.html