题解 | #【模板】动态区间和Ⅰ ‖ 单点修改 + 区间查询#

题目链接

【模板】动态区间和Ⅰ ‖ 单点修改 + 区间查询

题目描述

给定一个长度为 $n$ 的数组，我们需要实现一个数据结构来支持以下两种操作：

单点修改：将第 $x$ 个位置的元素增加 $k$ 。
区间查询：查询区间 $[l, r]$ 内所有元素的和。

输入:

第一行包含两个整数 $n$ 和 $m$ ，分别表示数组的长度和操作的次数。
第二行包含 $n$ 个整数，表示数组的初始元素。
接下来 $m$ 行，每行描述一个操作。格式为 1 x k 或 2 l r。

输出:

对于每个查询操作，输出一行，表示对应区间的元素和。

解题思路

本题是典型的数据结构问题，要求在支持单点修改的同时，能够快速查询区间和。树状数组（Fenwick Tree）是解决此类问题的经典数据结构。

树状数组通过一种巧妙的方式将前缀和存储在数组中，使得单点修改和前缀和查询的时间复杂度都能达到 $\mathcal{O}(\log n)$ 。

核心思想如下：

lowbit 操作：对于一个正整数 $x$ ，lowbit(x) 定义为 $x$ 的二进制表示中最低位的 $1$ 所代表的值。例如，lowbit(6) (二进制 110) 是 2 (二进制 10)。在代码中，它可以通过位运算 x & -x 来高效计算。
add(x, k) 操作：当我们要将原数组第 $x$ 个元素增加 $k$ 时，需要更新树状数组中所有包含这个点的区间。这可以通过不断地给 $x$ 加上 lowbit(x) 来找到所有相关的节点，并更新它们的值。
query(x) 操作：查询前缀和（从第 $1$ 个到第 $x$ 个元素的和），可以通过不断地从 $x$ 中减去 lowbit(x)，并将沿途节点的值累加起来得到。
区间和查询：对于区间 $[l, r]$ 的和，我们可以利用前缀和的思想来计算，即 query(r) - query(l - 1)。

通过这几个操作，我们就可以在 $\mathcal{O}(m \cdot \log n)$ 的时间内完成所有的操作。

代码

c++
java
python

#include <iostream>
#include <vector>

using namespace std;

using LL = long long;

int n;
vector<LL> tr;

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

void add(int x, LL k) {
    for (int i = x; i <= n; i += lowbit(i)) {
        tr[i] += k;
    }
}

LL query(int x) {
    LL res = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        res += tr[i];
    }
    return res;
}

int main() {
    int m;
    cin >> n >> m;
    tr.resize(n + 1);
    
    // 初始化树状数组
    for (int i = 1; i <= n; i++) {
        LL x;
        cin >> x;
        add(i, x);
    }
    
    while (m--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            add(x, y);
        } else {
            cout << query(y) - query(x - 1) << "\n";
        }
    }
    
    return 0;
}

import java.util.Scanner;

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

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

    static void add(int x, long k) {
        for (int i = x; i <= n; i += lowbit(i)) {
            tr[i] += k;
        }
    }

    static long query(int x) {
        long res = 0;
        for (int i = x; i > 0; i -= lowbit(i)) {
            res += tr[i];
        }
        return res;
    }

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

        // 初始化树状数组
        for (int i = 1; i <= n; i++) {
            long val = sc.nextLong();
            add(i, val);
        }

        while (m-- > 0) {
            int op = sc.nextInt();
            int x = sc.nextInt();
            int y = sc.nextInt();
            if (op == 1) {
                add(x, y);
            } else {
                System.out.println(query(y) - query(x - 1));
            }
        }
    }
}

import sys

def lowbit(x):
    return x & -x

def add(x, k):
    while x <= n:
        tr[x] += k
        x += lowbit(x)

def query(x):
    res = 0
    while x > 0:
        res += tr[x]
        x -= lowbit(x)
    return res

n, m = map(int, input().split())
a = list(map(int, input().split()))
tr = [0] * (n + 1)

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

for _ in range(m):
    line = input().split()
    op = int(line[0])
    x = int(line[1])
    y = int(line[2])
    
    if op == 1:
        add(x, y)
    else:
        print(query(y) - query(x - 1))

算法及复杂度

算法：树状数组（Binary Indexed Tree）
时间复杂度：初始建树为 $\mathcal{O}(n \cdot \log n)$ ，共有 $m$ 次操作，每次操作为 $\mathcal{O}(\log n)$ ，总时间复杂度为 $\mathcal{O}(n \cdot \log n + m \cdot \log n)$ 。
空间复杂度：需要一个数组来存储树状数组，大小为 $n+1$ ，所以空间复杂度为 $\mathcal{O}(n)$ 。