在差分数组上用 Fenwick 做两个端点修改，前缀和恢复单点值。
OJ: luogu
题目 ID: P3368
难度:普及+/提高-
标签:树状数组差分区间修改python
创建: 2026-07-16 21:00
更新: 2026-10-07 12:15
前置题目
luogu P2367语文成绩B 的区间加单点查把 A 教的差分两端点修改逐字搬进树状数组（d[l]+=x、d[r+1]-=x，位置值是差分前缀和），再叠加 Fenwick 维护与越界 r+1 判断roj 1547「一本通 4.3 例 1」区间和B 的 add/prefix 与 A 教的 Fenwick 单点修改上跳、前缀下跳模板逐字相同（代码里都是 index += index & -index 与 index -= index & -index），B 只是把维护对象换成差分数组，再叠加 A 未教的「区间加=两端点差分修改」这一步。roj 1535「一本通 4.1 例 1」数列操作B 复用 A 教的沿 lowbit 向上 add、向下 prefix 的 Fenwick 模板，只是把维护对象从原数组换成差分数组，从而把单点加/区间查对偶成区间加/单点查。
后置题目
roj 1416矩形覆盖计数B 的 y 方向做的正是「区间加、单点查」，A 提供差分 + 树状数组这一步；B 在此之上叠加按 x 排序的事件扫描与坐标离散化，并靠「同 x 先处理事件再回答询问」实现半开区间。roj 1561「一本通 4.5 练习 1」树上操作B 在 DFS 序与贡献视角、depth 拆项之后，把全部操作落到 A 教的差分树状数组区间加、点查上，单点加/子树加/询问都复用该模板roj 1539「一本通 4.1 练习 2」简单题B 直接套用 A 教的差分+树状数组框架：把区间操作化归为两个端点修改、用前缀操作求单点，只是把加法换成异或并把区间加换成区间翻转luogu P1438无聊的数列B 的解法一把等差数列拆成常数系数与下标系数后，两次复用 A 教的差分两端点修改 + Fenwick 前缀和恢复单点值，再叠加拆系数观察与双 Fenwick 组合luogu P5250【深基17.例5】木材仓库B 复用 A 的 Fenwick 单点加与前缀和查询模板维护长度存在性，再叠加离散化与树状数组上二分求第 k 小的前驱后继luogu P1083[NOIP 2012 提高组] 借教室B 的可行性检查复用 A 教的「区间加塌缩成差分两端修改、前缀和还原」这一步（前 k 份订单的区间借教室一次差分累加后前缀和即每日总量），再叠加 A 未教的二分答案与按天判超限的单调性判定。
题意
支持区间整体加值，以及查询某个位置当前值。
思路
维护差分 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))复杂度
每次操作
总结
区间加、单点查应先想到差分；Fenwick 维护的不是原数组，而是差分数组。
