【模板】树状数组 1

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

Fenwick 维护单点增量与前缀和，用两个前缀和相减回答区间和。

OJ: luogu

题目 ID: P3374

难度:普及/提高-

标签:树状数组前缀和模板题python

日期: 2026-07-16 21:00

目录

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

题意

支持某一项加值，以及查询任意闭区间元素和。

思路

Fenwick 节点保存一段由 lowbit 决定的后缀和。修改下标时不断加 lowbit，查询前缀时不断减 lowbit；区间 [l,r] 等于 prefix(r)-prefix(l-1)。

Python 知识

  • 自定义 os.read 分块整数生成器避免 150 万级 token 的 split 内存峰值。
  • array("q") 用 64 位整数紧凑保存树。
  • i & -i 取得最低位 1。

代码

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


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

复杂度

初始化与每次操作 O(log⁡n)O(\log n)，空间 O(n)O(n)。

总结

Fenwick 是动态前缀和的最短模板，区间查询仍通过前缀差完成。