题解：SP14543 RANGESUM - Range Sum

原题Link

好玩的题。

题目大意

给定一个长度为 $n$ 的序列，有 $Q$ 个操作。若 $op=1$，则求 $[l,r]$ 的区间和，否则将 $x$ 放在序列最前面。

Solution

看到 $1\le N,Q\le 10^5$，发现根据题意暴力模拟，最坏的时间复杂度是 $O(QN)$，明显不可以过。

考虑优化。

发现这题有一个区间求和操作，发现可能是用前缀和别问我为什么不是用树状数组和线段树，问就是这题是橙。

那可能又有人问了：你这不是瞎搞吗？前缀和不是只能维护静态区间吗？你这题的区间会变化呀，每次都要重新预处理，不是很慢吗？ 我刚开始看到这一也是这么想的，但是想了一想，发现，前缀和从数组头开始的预处理是 $O(n)$ 的，但是如果你只在前缀和的末尾加上一个数，它还是 $O(1)$ 的。

现在只需要把数组反转，就可以实现到 $O(N+Q)$ 的复杂度了。