题解：序列更新与区间查询问题

算法标签

• 树状数组（Binary Indexed Tree）
• 差分思想
• 前缀和
• 离线计算

问题分析

题目要求处理一个整数序列上的两种操作：添加区间更新三元组、查询区间和。关键挑战在于：每执行完一个操作后，列表中所有三元组都会对序列进行一次区间更新。若直接模拟该过程，每次操作后需遍历所有三元组，时间复杂度为 $O(m^2)$，无法应对 $10^5$ 级别的数据规模。

核心思路

三元组的贡献次数分析

设总操作数为 $m$，第 $t$ 个操作（0-based）加入的三元组 $(L, R, x)$，会在后续操作结束后被执行多次：

• 从第 $t$ 个操作结束后，到第 $m-1$ 个操作结束后，共执行 $(m - t)$ 次。
• 当处理第 $i$ 个操作（操作2）时，该三元组已执行 $(i - t)$ 次（仅当 $t < i$ 时）。

区间和的数学表达

对于操作 $i$ 中的查询 $[L, R]$，区间和可分解为：

1. 初始序列的区间和 $sum_{init}$。
2. 所有在 $t < i$ 时加入的三元组对 $[L, R]$ 的贡献总和 $sum_{triple}$。

其中，$sum_{triple}$ 可表示为：

$$sum_{triple} = \sum_{t < i} x_t \cdot (i - t) \cdot cnt_t $$

其中 $cnt_t$ 是 $[L, R]$ 与三元组 $(L_t, R_t, x_t)$ 区间的交集长度。

转化为高效计算

将 $(i - t)$ 拆分为 $i - t$，则：

$$sum_{triple} = i \cdot \sum(x_t \cdot cnt_t) - \sum(x_t \cdot t \cdot cnt_t) $$

通过两个树状数组分别维护以下信息，可快速计算上式：

• $f1$：维护 $x_t \cdot (m - t - 1) \cdot cnt_t$ 的总和（用于转化系数）。
• $f2$：维护 $x_t \cdot cnt_t$ 的总和。

代码解析

树状数组实现

树状数组（bit 结构）支持高效的区间更新和区间查询，通过差分思想实现：

• update(l, r, v)：对区间 $[l, r]$ 增加 $v$。
• sum(l, r)：查询区间 $[l, r]$ 的总和。

主逻辑

1. 初始化：用 $f1$ 存储初始序列（每个元素视为区间 $[i, i]$ 的更新）。
2. 处理操作：
   • 操作1（添加三元组）：在 $f1$ 中添加 $x \cdot (m - t - 1)$ 到区间 $[L, R]$，在 $f2$ 中添加 $x$ 到区间 $[L, R]$（$t$ 为当前操作索引）。
   • 操作2（查询）：计算 $f1.sum(L, R) - f2.sum(L, R) \cdot (m - i - 1)$，其中 $i$ 为当前操作索引，该式等价于所需区间和。

复杂度分析

• 每个操作（1或2）均通过树状数组进行区间更新或查询，时间复杂度为 $O(\log n)$。
• 总时间复杂度为 $O(m \log n)$，可处理 $10^5$ 级别的数据规模。

完整代码

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

using i64 = long long;

template<class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmin(T &a, const T &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

inline int lowbit(int x) {
    return x & (-x);
}

struct bit {
    int n;
    vector<i64> c1, c2;

    inline bit() {}
    inline bit(int _n): n(_n) {
        c1.resize(n);
        c2.resize(n);
    }

    inline void add(int x, i64 k) {
        for (int i = x + 1; i <= n; i += lowbit(i)) {
            c1[i - 1] += k;
            c2[i - 1] += k * x;
        }
    }

    inline i64 ask(int x) {
        i64 res = 0;
        for (int i = x + 1; i; i -= lowbit(i)) {
            res += c1[i - 1] * (x + 1) - c2[i - 1];
        }
        return res;
    }

    inline void update(int l, int r, i64 v) {
        add(l, v);
        add(r + 1, -v);
    }

    inline i64 sum(int l, int r) {
        return ask(r) - ask(l - 1);
    }
};

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int n;
    scanf("%d", &n);
    bit f1(n), f2(n);

    for (int i = 0, x; i < n; i++) {
        scanf("%d", &x);
        f1.update(i, i, x);
    }

    int m;
    scanf("%d", &m);

    for (int i = 0, op, l, r, x; i < m; i++) {
        scanf("%d %d %d", &op, &l, &r);
        l--, r--;

        if (op == 1) {
            scanf("%d", &x);
            f1.update(l, r, 1LL * x * (m - i - 1));
            f2.update(l, r, x);
        } else {
            printf("%lld\n", f1.sum(l, r) - f2.sum(l, r) * (m - i - 1));
        }
    }

    return 0;
}