题目链接

PEEK67 区间增量与单点求值

题目描述

给定一个长度为 的数组 。你需要支持两种操作：

  1. 区间增量：将区间 内的所有元素都加上一个值 。
  2. 单点求值：查询下标为 的元素 的值。

解题思路

本题包含对区间的动态修改和对单点的查询，是数据结构领域的经典问题。如果使用朴素数组，区间修改的复杂度为 ，在大量操作下会超时。

解决此问题的标准高效方法是利用 差分数组 (Difference Array) 和 树状数组 (Fenwick Tree / Binary Indexed Tree)。

  1. 差分数组

    我们不直接维护原数组 ，而是维护它的差分数组 ，其中 (约定 )。

    • 性质：原数组中的任意一个元素 的值，等于其差分数组的前缀和，即 。
    • 基于这个性质，对 的单点查询就转化为了对 的前缀和查询。

  2. 将区间修改转化为单点修改

    当我们对 的一个区间 内所有元素都加上 时，观察它对差分数组 的影响：

    • 对于 ：。
    • 对于 ：，值不变。
    • 对于 (若 )：。 因此，对 的区间 增量操作，等价于对 的两次单点修改： 增加 ， 减少 。

  3. 树状数组

    树状数组是维护单点修改和前缀和查询的绝佳工具，两项操作的复杂度均为 。这完美契合了我们将原问题转化后的需求。

算法流程

  1. 初始化：根据初始数组 计算出其差分数组 ，并用 的值来构建树状数组。
  2. 区间增量 (l, r, x)：对树状数组执行两次单点更新：add(l, x) 和 add(r+1, -x)。
  3. 单点求值 (p)：对树状数组执行一次前缀和查询：query(p)。

代码

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 500005;
long long bit[MAXN];
int n;

void add(int idx, long long delta) {
    for (; idx <= n; idx += idx & -idx) {
        bit[idx] += delta;
    }
}

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

int main() {
    int m;
    cin >> n >> m;

    vector<long long> a(n + 1);
    long long last = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        add(i, a[i] - last);
        last = a[i];
    }

    for (int i = 0; i < m; ++i) {
        int type;
        cin >> type;
        if (type == 1) {
            int l, r;
            long long x;
            cin >> l >> r >> x;
            add(l, x);
            if (r + 1 <= n) {
                add(r + 1, -x);
            }
        } else {
            int p;
            cin >> p;
            cout << query(p) << "\n";
        }
    }

    return 0;
}

import java.util.Scanner;

public class Main {
    static final int MAXN = 500005;
    static long[] bit = new long[MAXN];
    static int n;

    static void add(int idx, long delta) {
        for (; idx <= n; idx += idx & -idx) {
            bit[idx] += delta;
        }
    }

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int m = sc.nextInt();

        long[] a = new long[n + 1];
        long last = 0;
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextLong();
            add(i, a[i] - last);
            last = a[i];
        }

        for (int i = 0; i < m; i++) {
            int type = sc.nextInt();
            if (type == 1) {
                int l = sc.nextInt();
                int r = sc.nextInt();
                long x = sc.nextLong();
                add(l, x);
                if (r + 1 <= n) {
                    add(r + 1, -x);
                }
            } else {
                int p = sc.nextInt();
                System.out.println(query(p));
            }
        }
    }
}

def solve():
    n, m = map(int, input().split())
    a = [0] + list(map(int, input().split()))
    
    bit = [0] * (n + 1)

    def add(idx, delta):
        while idx <= n:
            bit[idx] += delta
            idx += idx & -idx

    def query(idx):
        s = 0
        while idx > 0:
            s += bit[idx]
            idx -= idx & -idx
        return s

    # 初始化树状数组
    for i in range(1, n + 1):
        add(i, a[i] - a[i-1])

    results = []
    for _ in range(m):
        line = list(map(int, input().split()))
        op_type = line[0]
        
        if op_type == 1:
            l, r, x = line[1], line[2], line[3]
            add(l, x)
            if r + 1 <= n:
                add(r + 1, -x)
        else:
            p = line[1]
            results.append(str(query(p)))
            
    if results:
        print("\n".join(results))

solve()

算法及复杂度

  • 算法：差分数组 + 树状数组 (Fenwick Tree)
  • 时间复杂度：。初始化树状数组需要 （或者通过 的方式），后续 次操作每次需要 。
  • 空间复杂度：，用于存储树状数组。