维护一个长为 $n$ 的序列，$q$ 次操作：

• $1 \ l \ r \ k$，询问区间内所有小于等于 $k$ 的数的和。

• $2 \ x \ k$，将第 $x$ 个数修改为 $k$。

其中 $1 \le n \le 5 \times 10^5,1 \le q \le 10^5$，且序列中任何时刻的最大值 $Max$ 都满足 $1 \le Max \le 10^5$。

问一下：这题除了用树状数组套可持久化线段树（值域线段树）还有什么其他的做法吗？

即有没有比 $O(N \log^2 W)$（$W$ 为值域）更优秀的算法？