题解 | #区间增量与单点求值#

题目链接

区间增量与单点求值

题目描述

给定一个长度为 $n$ 的数组，需要支持两种操作：

区间增量：将区间 $[l, r]$ 内的所有元素加上一个值 $x$ 。
单点求值：查询下标为 $p$ 的元素的值。

解题思路

这是一个经典的数据结构问题，要求我们实现“区间更新”和“单点查询”。解决此类问题的标准方法之一是使用 差分数组 配合 树状数组 (Fenwick Tree)。

差分数组
- 首先，我们引入差分的思想。对于原数组 $a$ ，我们构建一个差分数组 $d$ ，使得： $d_1 = a_1$ $d_i = a_i - a_{i-1}$ (对于 $i > 1$ )
- 从这个定义可以看出，原数组 $a$ 的任意一项 $a_p$ 都可以表示为差分数组 $d$ 的一个前缀和：
  
  $a_p = \sum_{i=1}^{p} d_i$
- 这样，对 $a$ 的单点查询就转化为了对 $d$ 的区间和查询。
转化区间更新
- 接下来，我们分析“区间增量”操作对差分数组 $d$ 的影响。将区间 $[l, r]$ 的所有元素加上 $x$ ：
  - 对于 $a_l$ ，其值变为 $a_l + x$ 。这使得 $d_l = (a_l+x) - a_{l-1} = (a_l - a_{l-1}) + x$ 。即 $d_l$ 增加了 $x$ 。
  - 对于任意 $i \in (l, r]$ ， $a_i$ 和 $a_{i-1}$ 都增加了 $x$ ，所以它们的差 $d_i = (a_i+x) - (a_{i-1}+x)$ 保持不变。
  - 对于 $d_{r+1}$ ，其值变为 $d_{r+1} = a_{r+1} - (a_r+x) = (a_{r+1} - a_r) - x$ 。即 $d_{r+1}$ 减少了 $x$ 。
- 综上，对 $a$ 的区间 $[l, r]$ 增量操作，转化为了对 $d$ 的两次单点更新： $d_l$ 加上 $x$ ， $d_{r+1}$ 减去 $x$ 。
树状数组
- 经过转化，原问题变成了对一个新数组（差分数组 $d$ ）进行“单点更新”和“前缀和查询”。
- 这正是树状数组最擅长解决的问题。我们可以用一个树状数组来维护差分数组 $d$ ，使得单点更新和前缀和查询的复杂度都为 $O(\log n)$ 。

综上，我们通过差分思想将问题巧妙地转化为树状数组的经典应用，从而高效地解决了问题。

代码

c++
java
python

#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

vector<ll> bit;
int n;

void update(int i, ll x) {
    for (; i <= n + 1; i += i & -i) {
        bit[i] += x;
    }
}

ll query(int i) {
    ll sum = 0;
    for (; i > 0; i -= i & -i) {
        sum += bit[i];
    }
    return sum;
}

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

    int q;
    cin >> n >> q;
    bit.assign(n + 2, 0); 
    
    ll prev = 0;
    for (int i = 1; i <= n; ++i) {
        ll current;
        cin >> current;
        update(i, current - prev);
        prev = current;
    }

    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int l, r;
            ll x;
            cin >> l >> r >> x;
            update(l, x);
            update(r + 1, -x);
        } else {
            int p;
            cin >> p;
            cout << query(p) << "\n";
        }
    }
    return 0;
}

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Main {
    static long[] bit;
    static int n;

    static void update(int i, long x) {
        for (; i <= n + 1; i += i & -i) {
            bit[i] += x;
        }
    }

    static long query(int i) {
        long sum = 0;
        for (; i > 0; i -= i & -i) {
            sum += bit[i];
        }
        return sum;
    }

    public static void main(String[] args) throws Exception {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(System.out);
        in.nextToken();
        n = (int) in.nval;
        in.nextToken();
        int q = (int) in.nval;
        bit = new long[n + 2];

        long prev = 0;
        for (int i = 1; i <= n; ++i) {
            in.nextToken();
            long current = (long) in.nval;
            update(i, current - prev);
            prev = current;
        }

        for (int k = 0; k < q; ++k) {
            in.nextToken();
            int op = (int) in.nval;
            if (op == 1) {
                in.nextToken();
                int l = (int) in.nval;
                in.nextToken();
                int r = (int) in.nval;
                in.nextToken();
                long x = (long) in.nval;
                update(l, x);
                update(r + 1, -x);
            } else {
                in.nextToken();
                int p = (int) in.nval;
                out.println(query(p));
            }
        }
        out.flush();
    }
}

n, q = 0, 0
bit = []

def update(i, x):
    """单点更新"""
    while i <= n + 1:
        bit[i] += x
        i += i & -i

def query(i):
    """前缀和查询"""
    s = 0
    while i > 0:
        s += bit[i]
        i -= i & -i
    return s

def main():
    global n, q, bit
    line1 = list(map(int, input().split()))
    n, q = line1[0], line1[1]

    bit = [0] * (n + 2)
    
    a = list(map(int, input().split()))
    
    prev = 0
    for i in range(n):
        update(i + 1, a[i] - prev)
        prev = a[i]

    for _ in range(q):
        line = list(map(int, input().split()))
        op = line[0]
        if op == 1:
            l, r, x = line[1], line[2], line[3]
            update(l, x)
            update(r + 1, -x)
        else:
            p = line[1]
            print(query(p))

if __name__ == "__main__":
    main()

算法及复杂度

算法：差分数组 + 树状数组 (Fenwick Tree)
时间复杂度： $O((n+q)\log n)$ ，其中初始化树状数组需要 $O(n \log n)$ ，每次操作需要 $O(\log n)$ 。
空间复杂度： $O(n)$ ，用于存储树状数组。