小清新线段树

通常来说，在使用线段树维护区间操作时，需要使操作在区间上能被快速计算，经典的区间加-区间求和是一个简单的例子。

但是，这里也有一个看似难以维护的反例：

bzoj 3211 花神游历各国

维护一个序列 $A$，初始值为 $A=(a_1,a_2,a_3,\cdots,a_n)$，支持以下操作 $q$ 次：

1. 区间求和
2. 对区间每个数求平方根（向下取整）

$1\le n,q\le 1\times 10^5,0\le a_i\le 10^{12}.$

维护这种数据的线段树被称为小清新线段树。

小清新线段树的概念由 $\textcolor{red}{\text{jiry_2}}$ 提出，命名与 $\text{ZKW}$（重口味）线段树¹ 相对。是一类结合势能分析以及懒标记应用的非传统线段树。

区间求平方根显然很难在非叶节点上维护，我们考虑暴力。

即，对于整个区间求平方根的操作，我们暴力地向它的两个子节点下传操作。

这样做的时间复杂度有保证吗？有！

由于只有开根操作，最终的结果非 $1$ 即 $0$；当区间内均为 $1$ 或 $0$ 时，我们无需对这个块再做处理。对于 $N>1$，所需的操作次数是 $O(\log\log n)$ 级别的。

我们定义势能函数 $f(A)=\sum_{a\in A}c(a)$，其中 $c(a)$ 表示将 $a$ 降为 $0$ 或 $1$ 的次数。

最劣情况下，结束时的势能 $f(A_e)=0$，而最开始要花费代价将势能升至 $f(A_s)=O(n\log\log \max a_i)$，因此维护区间平方根的总复杂度为 $O(n\log\log\max a_i)$.

维护区间和的复杂度为 $O(q\log n)$.

因此总的复杂度为 $O(q\log n+n\log\log\max a_i)$.

这种思路也可以处理区间取欧拉函数、区间取模、区间整除、区间对一个数取 $\min$ 等抽象操作，具体实现和复杂度需要具体分析。