【模板】树状数组 2

GitHub跳转原题关系图返回列表

在差分数组上用 Fenwick 做两个端点修改，前缀和恢复单点值。

OJ: luogu

题目 ID: P3368

难度:普及/提高-

标签:树状数组差分区间修改python

日期: 2026-07-16 21:00

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

支持区间整体加值，以及查询某个位置当前值。

思路

维护差分 d[i]=a[i]-a[i-1]。区间 [l,r] 加 x 只需 d[l]+=x、d[r+1]-=x；原数组位置 p 是差分前缀和。

Fenwick 正好支持两个差分点修改与前缀查询。初始数组读入时相邻相减后加入树。

Python 知识

  • 流式读入时只保存 previous 就能构造差分，不必保留原数组。
  • if right < n 避免修改越界的 r+1。
  • 与 P3374 共用相同 add/prefix 模板，含义由维护对象决定。

代码

python
import os
import sys
from array import array


def integers():
    number = 0
    sign = 1
    reading = False
    while chunk := os.read(0, 1 << 20):
        for byte in chunk:
            if byte == 45:
                sign = -1
            elif 48 <= byte <= 57:
                number = number * 10 + byte - 48
                reading = True
            elif reading:
                yield sign * number
                number, sign, reading = 0, 1, False
    if reading:
        yield sign * number


data = iter(integers())
n, operation_count = next(data), next(data)
tree = array("q", [0]) * (n + 1)


def add(index, value):
    while index <= n:
        tree[index] += value
        index += index & -index


def prefix(index):
    result = 0
    while index:
        result += tree[index]
        index -= index & -index
    return result


previous = 0
for i in range(1, n + 1):
    value = next(data)
    add(i, value - previous)
    previous = value
answers = []
for _ in range(operation_count):
    operation, left = next(data), next(data)
    if operation == 1:
        right, value = next(data), next(data)
        add(left, value)
        if right < n:
            add(right + 1, -value)
    else:
        answers.append(str(prefix(left)))
print("\n".join(answers))

复杂度

每次操作 O(log⁡n)O(\log n)，空间 O(n)O(n)。

总结

区间加、单点查应先想到差分；Fenwick 维护的不是原数组，而是差分数组。