Fenwick 维护单点增量与前缀和，用两个前缀和相减回答区间和。
OJ: luogu
题目 ID: P3374
难度:普及+/提高-
标签:树状数组前缀和模板题python
创建: 2026-07-16 21:00
更新: 2026-10-07 12:15
后置题目
roj 1561「一本通 4.5 练习 1」树上操作B 的最后一层——单点加/子树加/询问全部化为差分树状数组的区间加与点查，A 正是点查即前缀和的 Fenwick 前缀和维护（B 的 bit_add/bit_sum 与 A 的 add/prefix 同构，且 B 把单点加教成子树内每个 y 统一 +a 的区间加），B 在此模板上叠加 DFS 序、贡献视角与 depth 拆两树，故 A 是纯模板、B 在 A 之上叠加额外流程。roj 1539「一本通 4.1 练习 2」简单题B 的异或树状数组把 A 教的 Fenwick「单点改沿加 lowbit 上跳、前缀查沿减 lowbit 下拆」原样复用（代码 flip/prefix_xor 与 A 的 add/prefix 同一条 lowbit 链），只把加法换成异或，再叠加 A 未教的异或差分把区间翻转降成两次单点取反。luogu P2345[USACO04OPEN] MooFest GB 沿用 A 的树状数组单点修改与前缀和查询模板维护数量、坐标和，再叠加按听力排序消掉 max 与绝对值拆左右luogu P1438无聊的数列B 的解法一把常数系数与下标系数的差分各交给一个 Fenwick，直接复用 A 的「lowbit 单点修改+前缀和查询」这一步树状数组机制，再叠加等差数列拆系数luogu P1637三元上升子序列B 的两次扫描计数复用 A 的树状数组单点修改与前缀查询这一步（left[i]=前缀和(rk[i]-1) 数左侧更小个数、插入排名更新树），再叠加 A 未教的固定中间点拆分、贡献法乘法合并与严格排除相等值的排名处理。luogu P2161[SHOI2009] 会场预约B 的 kth 二进制提升正是建立在 A 教的「tree[x] 保存 lowbit 决定的段和、沿 lowbit 增删与查询」这一步之上（整段跳过即段和比较），再叠加 0/1 存在桶、前驱后继与区间不交删除流程。luogu P5250【深基17.例5】木材仓库B 复用 A 的树状数组单点修改与前缀和查询模板维护库存存在性，再叠加离散化与树上二分求第 k 小的前驱后继luogu P2234[HNOI2002] 营业额统计B 复用 A 教的「Fenwick 单点加、前缀和查询」这一步（计数树前缀和得 less 后用 kth 找前后继），再叠加 A 未教的离散化排名、kth 二进制倍增与重复值波动为零的处理。luogu P1972[SDOI2009] HH 的项链B 复用 A 的树状数组单点修改加前缀差求和步骤，按右端点离线维护每色最后位置回答区间颜色数luogu P5200[USACO19JAN] Sleepy Cow Sorting GB 用 A 教的 Fenwick 点加 + 前缀和查询维护值域出现次数（sum(a[i]) 得有序集合里比它小的个数），再叠加最长严格递增后缀观察与逐步插入的步数公式
题意
支持某一项加值，以及查询任意闭区间元素和。
思路
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))复杂度
初始化与每次操作
总结
Fenwick 是动态前缀和的最短模板，区间查询仍通过前缀差完成。
