差分数组与区间累加查询的C++高效实现详解

## 📝 问题解析 需要处理区间累加操作和区间求和查询，n<100，q和x规模未明确，但可用**差分数组**将O(nq)优化为O(q+n)，再通过前缀和快速回答单次查询。 ## 💻 C++ 实现 ```cpp #include <bits/stdc++.h> using namespace std; int main() { int n, q; cin >> n >> q; vector<long long> diff(n + 2, 0); // 差分数组，下标从1到n+1 while (q--) { int L, R; long long x; cin >> L >> R >> x; diff[L] += x; diff[R + 1] -= x; } // 还原每朵花的浇水次数 vector<long long> cnt(n + 1, 0); for (int i = 1; i <= n; ++i) { cnt[i] = cnt[i - 1] + diff[i]; } // 前缀和数组，便于区间求和 vector<long long> pre(n + 1, 0); for (int i = 1; i <= n; ++i) { pre[i] = pre[i - 1] + cnt[i]; } int b, y; cin >> b >> y; cout << pre[y] - pre[b - 1] << '\n'; return 0; } ``` ## 🔍 代码说明 - 差分数组`diff`记录区间增量，`diff[L] += x, diff[R+1] -= x`。 - 对差分数组求前缀和得到每朵花的浇水次数`cnt[i]`。 - 再对`cnt`求前缀和`pre`，即可O(1)回答`[b, y]`区间和。 - 注意使用`long long`防止溢出。 ## 🧪 示例验证 输入： ``` 5 2 1 3 2 2 4 1 2 4 ``` 过程： - 第一轮：1~3加2 - 第二轮：2~4加1 - 每朵花次数：2, 3, 3, 1, 0 - 查询2~4：3+3+1=7 输出：`7` ######[AI问答 | 541点数解答 | 2026-08-02 15:43:08]