自己想的一道数据结构，题目如下：

给定正整数 $n$ 和一个关于 $1\sim n$ 的排列 $b_1,b_2,..., b _ n$。

要求维护一个数列 $a_1,a_2,...,a_n$，初值全为 $0$，有两种操作：

• 给定 $l,r,x$，把 $a_l,a_{l+1},...,a_{r-1},a_r$ 都加上 $x$；

• 给定 $l,r$，求出 $a_{b_l},a_{b_{l+1}},...,a_{b_{r-1}},a_{b_r}$ 的和。

其中 $1\le n,m\le 10^5$，$m$ 是操作数，保证任何时刻的 $a_i$ 的绝对值不超过 $1000$。

在 $\{b_n\}$ 随机生成时，存在 $O(n\log ^2n)$ 的做法。但是在刻意构造下会变成 $O(n^2\log n)$，因此想问问有没有更好的解法。