这道题和你之前那个 “区间加，单点查” 的思路完全相同地要用 差分数组，但它多了一个“内层前缀和”的需求——你要查的是

$\sum_{i=1}^x a_i$

而不是某个点 $a_x$ 本身。用差分 $d[i]=a[i]-a[i-1]$ 的话，

$ a_i=\sum_{j=1}^i d[j]\,,\qquad \sum_{i=1}^x a_i =\sum_{i=1}^x\sum_{j=1}^i d[j] =\sum_{j=1}^x d[j]\,(x-j+1). $

这就不再是“给点打标记、查一次前缀和”那么简单了——你要算的是一个带权的前缀和。

---

📊 解决办法：双树状数组

我们用 两棵 Fenwick Tree（记作 $B_1$ 和 $B_2$）来实现「区间加」和「[1…x] 区间和」：

1. 区间加 $[l,r]$ 加 $d$：

   B1.add(l,  d);
   B1.add(r+1, -d);
   B2.add(l,  d*(l-1));
   B2.add(r+1, -d*r);
   

2. 查询前缀和 $\sum_{i=1}^x a_i$：

   $$ S(x) = \sum_{i=1}^x a_i = \sum_{i=1}^x \Bigl[\sum_{j=1}^i d[j]\Bigr] = \sum_{j=1}^x d[j]\,(x-j+1) = x\sum_{j=1}^x d[j] \;-\; \sum_{j=1}^x d[j](j-1). $$

   而

   $$ \sum_{j=1}^x d[j] = B1.sum(x), \quad \sum_{j=1}^x d[j](j-1) = B2.sum(x). $$

   所以

   long long sum1 = B1.sum(x);
   long long sum2 = B2.sum(x);
   answer = sum1 * x - sum2;
   

---

对比之前的变化

方面	老题（区间加 + 单点查）	新题（区间加 + 前缀和查）
差分维护	一个 BIT 保存 $d[i]$	两个 BIT 保存 $d[i]$ 和 $d[i]\times(i-1)$
查询	直接 a[x] = sumBIT(x)	需要计算带权前缀：sum1*x - sum2
复杂度	$\;O(\log n)$	$\;O(\log n)$（常数大一倍）

---

小结

• 变化：查询从“点”变成了“[1…x] 的和”，于是差分累加外又套了一层累加（权重是 $x-j+1$）。
• 解决：再用一棵 BIT 维护 $\sum d[j](j-1)$，加上原来那棵，就能做到所有操作都是 $O(\log n)$。

---

---

---

我们把这个二重求和换个顺序，就能看到每个 $d[j]$ 出现的次数是如何得到 “$(x - j + 1)$” 的。

---

原式

$$\sum_{i=1}^{x}\;\sum_{j=1}^{i} d[j].$$

这里，外层 $i$ 从 1 到 $x$，内层 $j$ 从 1 到 $i$。

---

换个角度看

对同一个 $j$ 来说，它会在那些 “$\sum_{j=1}^{i}$” 里被加进去呢？只有当 $i \ge j$ 时，内层才会把 $d[j]$ 累加一次。

• 如果 $j=1$，则它会出现在 $i=1,2,3,\dots,x$ 这 $x$ 项里；
• 如果 $j=2$，则出现在 $i=2,3,\dots,x$ 这 $x-1$ 项里；
• ……
• 如果一般地，是任意 $j$，它出现在从 $i=j$ 一直到 $i=x$，共 $x - j + 1$ 次。

---

数学化地交换求和顺序

1. 把两重求和上下调换（“换元”或叫 “Fubini 变换”）：

   $$\sum_{i=1}^{x}\;\sum_{j=1}^{i} d[j] = \sum_{j=1}^{x}\;\sum_{i=j}^{x} d[j]. $$

   这里我们交换了“先遍历 $i$ 再遍历 $j$”→“先遍历 $j$ 再遍历 $i$”的顺序。

2. 内层对 $i$ 的求和其实在加同一个常数 $d[j]$，所以

   $$\sum_{i=j}^{x} d[j] = d[j] \times (\text{出现的次数}) = d[j] \times (x - j + 1). $$

3. 合在一起就得：

   $$\sum_{j=1}^{x}\;\sum_{i=j}^{x} d[j] = \sum_{j=1}^{x} d[j]\,(x - j + 1). $$

---

小例子验证

取 $x=3$，差分数组 $\{d[1],d[2],d[3]\}$：

原式展开：

$$\sum_{i=1}^{3}\sum_{j=1}^{i}d[j] = \bigl[d_1\bigr] + \bigl[d_1 + d_2\bigr] + \bigl[d_1 + d_2 + d_3\bigr] = (d_1 + d_1 + d_1)\;+\;(d_2 + d_2)\;+\;(d_3) = 3d_1 + 2d_2 + 1d_3. $$

而根据公式：

$$\sum_{j=1}^{3}d[j]\,(3 - j + 1) = d_1\cdot3 + d_2\cdot2 + d_3\cdot1, $$

完全一致。

---

结论

$$\boxed{\sum_{i=1}^x\sum_{j=1}^i d[j] = \sum_{j=1}^x d[j]\,(x - j + 1).} $$

这正是把「先累加再累加」的二重和，等价于「对每个 $d[j]$ 按它出现的次数加权求和」。

树状数组方法2：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000 + 5;
int n, m;
long long c1[MAXN], c2[MAXN];

// lb：取最低位 1
inline int lb(int x) {
    return x & -x;
}

// 对树状数组 t，在 pos 位置加 v
void upd(long long t[], int pos, long long v) {
    for (; pos <= n; pos += lb(pos))
        t[pos] += v;
}

// 前缀和查询：sum t[1..pos]
long long pre(long long t[], int pos) {
    long long s = 0;
    for (; pos > 0; pos -= lb(pos))
        s += t[pos];
    return s;
}

// 区间 [l..r] 加 v
// 用两棵 BIT 实现区间更新 + 前缀查询
void radd(int l, int r, long long v) {
    // B1 做 +v/-v
    upd(c1, l, v);
    upd(c1, r+1, -v);
    // B2 做 -(l-1)*v / r*v
    upd(c2, l, -v*(l-1));
    upd(c2, r+1,  v*r);
}

// 查询 [1..x] 的总和
long long qsum(int x) {
    // sum = x*sum(c1[1..x]) + sum(c2[1..x])
    return pre(c1, x) * x + pre(c2, x);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    while (m--) {
        int k, l, r;
        long long d;
        cin >> k;
        if (k == 1) {
            cin >> l >> r >> d;
            radd(l, r, d);
        } else {
            cin >> r; // here r is x
            cout << qsum(r) << "\n";
        }
    }
    return 0;
}

普通方法，80分：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    vector<long long> diff(n + 2, 0); // 差分数组，下标1~n+1
    
    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            int l, r;
            long long d;
            cin >> l >> r >> d;
            diff[l] += d;
            if (r + 1 <= n) {
                diff[r + 1] -= d;
            }
        } else {
            int x;
            cin >> x;
            long long current = 0, sum = 0;
            // 暴力遍历计算前缀和的前缀和
            for (int i = 1; i <= x; ++i) { 
                current += diff[i];     // 计算当前值
                sum += current;          // 累加前缀和
            }
            cout << sum << '\n';
        }
    }
    
    return 0;
}