P4763 混合操作（基础）

解题思路

题目里有两种操作混在一起：第一种操作询问一个区间 [L,R] 的和，第二种操作把某个位置的数改成一个新值。题目特别说：修改操作一共只出现 1 次。抓住这个特点，题目就变得很简单了。

我们的计划分三步走。第一步，先按最原始的数组算出前缀和 pre[i]，这样在没有修改的情况下，询问区间 [L,R] 的和就是 pre[R] - pre[L-1]。第二步，一边读入操作一边处理：如果遇到询问操作，就用前缀和公式算出答案并输出；如果遇到修改操作（把位置 k 的数改成 num），先把这个位置 k 和新的值 num 记下来，但不急着改数组。第三步，之后如果再遇到询问，就要判断：如果被修改的位置 k 正好落在询问的区间 [L,R] 里面，那么在"原数组前缀和"的基础上，还要加上 (num - 原来位置 k 的值)，因为这一个数被改掉了；如果 k 不在区间里，就完全不影响这次询问，直接输出原答案。

用样例来检验：原始数组是 2 1 3 6 4 20 15 10 4 11。前两次询问没发生修改，直接用前缀和：1 3 7 的和是 48，1 4 9 的和是 59。第三次操作把第 8 个数改成 20（原来是 10）。第四次询问 1 7 10，原本按原数组算出的和是 40，但第 8 位在区间内，要加 (20-10)=10，得到 50；第五次询问 1 5 8，原和是 49，也加 10 得到 59。和样例输出完全一致。

这个做法的关键是"修改只有一次"，所以只需要记录一个位置和新值；如果修改很多次，就要用线段树等高级数据结构了。

参考代码

// 混合操作：前缀和求区间和，修改操作只有一次，遇到修改就记录新值，询问时补偿差值
#include <iostream>
int main() {
    int n;
    std::cin >> n;
    long long a[500005] = {0};  // 存每个位置的原始值
    long long pre[500005] = {0}; // pre[i] 表示前 i 个数的和
    for (int i = 1; i <= n; ++i) {
        std::cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }
    int m;
    std::cin >> m;
    int pos = -1;      // 被修改的位置，-1 表示还没发生修改
    long long nv = 0;  // 修改后的新值
    for (int i = 0; i < m; ++i) {
        int t;
        std::cin >> t;
        if (t == 1) {
            int L, R;
            std::cin >> L >> R;
            long long s = pre[R] - pre[L - 1]; // 用原数组算出的区间和
            // 若修改位置落在区间内，则补上 (新值 - 旧值)
            if (pos != -1 && pos >= L && pos <= R) s += nv - a[pos];
            std::cout << s << '\n';
        } else {
            int k;
            long long num;
            std::cin >> k >> num;
            pos = k;   // 记录修改位置
            nv = num;  // 记录修改后的值
        }
    }
    return 0;
}

复杂度分析

建前缀和需要 O(n) 时间；处理 m 次操作，询问和修改都只需要 O(1) 时间，所以总时间复杂度是 O(n+m)，空间复杂度是 O(n)（一个 a 数组加一个 pre 数组）。因为每次询问只做常数次计算，即使 n、m 都很大也能飞快运行。注意"修改只出现一次"这个条件，代码里用一个 pos 和 nv 就足够了。