OI-WIKI
前缀和方便查询区间和，差分方便进行区间修改
一维
前缀和
s
[
i
]
=
s
[
i
−
1
]
+
a
[
i
]
i
≥
2
s[i]=s[i-1]+a[i]\ \ \ \ \ \ i\geq2
s[i]=s[i−1]+a[i] i≥2
s
[
i
]
=
a
[
i
]
i
=
1
s[i]=a[i]\ \ \ \ \ \ \ i=1
s[i]=a[i] i=1
查询区间
[
l
,
r
]
[l,r]
[l,r]的
a
[
i
]
a[i]
a[i]和：
s
[
r
]
−
s
[
l
−
1
]
s[r]-s[l-1]
s[r]−s[l−1]
差分
a
[
i
]
=
s
[
i
]
−
s
[
i
−
1
]
i
≥
2
a[i]=s[i]-s[i-1]\ \ \ \ \ \ i\geq2
a[i]=s[i]−s[i−1] i≥2
a
[
i
]
=
s
[
i
]
i
=
1
a[i]=s[i]\ \ \ \ \ \ \ i=1
a[i]=s[i] i=1
区间
[
l
,
r
]
[l,r]
[l,r]的
s
[
i
]
s[i]
s[i]均加
v
v
v：
a
[
l
]
+
=
v
a[l]+=v
a[l]+=v
a
[
r
+
1
]
−
=
v
a[r+1]-=v
a[r+1]−=v
前缀和的前缀和
s
[
i
]
=
s
[
i
−
1
]
+
a
[
i
]
i
≥
2
s[i]=s[i-1]+a[i]\ \ \ \ \ \ i\geq2
s[i]=s[i−1]+a[i] i≥2
s
[
i
]
=
a
[
i
]
i
=
1
s[i]=a[i]\ \ \ \ \ \ \ i=1
s[i]=a[i] i=1
s
u
m
[
i
]
=
s
u
m
[
i
−
1
]
+
s
[
i
]
i
≥
2
sum[i]=sum[i-1]+s[i]\ \ \ \ \ \ i\geq2
sum[i]=sum[i−1]+s[i] i≥2
s
u
m
[
i
]
=
s
[
i
]
i
=
1
sum[i]=s[i]\ \ \ \ \ \ \ i=1
sum[i]=s[i] i=1
有
s
u
m
[
n
]
=
∑
i
=
1
n
s
[
i
]
=
∑
i
=
1
n
(
n
−
i
+
1
)
a
[
i
]
sum[n]=\sum_{i=1}^{n}s[i]=\sum_{i=1}^{n}(n-i+1)a[i]
sum[n]=∑i=1ns[i]=∑i=1n(n−i+1)a[i]
二维
容斥原理
定义
s
x
,
y
=
∑
i
=
1
x
∑
j
=
1
y
a
i
,
j
s_{x,y}=\sum_{i=1}^{x}\sum_{j=1}^{y}a_{i,j}
sx,y=∑i=1x∑j=1yai,j
则
s
x
,
y
=
s
x
−
1
,
y
+
s
x
,
y
−
1
−
s
x
−
1
,
y
−
1
+
a
x
,
y
s_{x,y}=s_{x-1,y}+s_{x,y-1}-s_{x-1,y-1}+a_{x,y}
sx,y=sx−1,y+sx,y−1−sx−1,y−1+ax,y
前缀和
求矩形的
a
a
a值和：
s
c
,
d
−
s
c
,
b
−
1
−
s
a
−
1
,
d
+
s
a
−
1
,
b
−
1
s_{c,d}-s_{c,b-1}-s_{a-1,d}+s_{a-1,b-1}
sc,d−sc,b−1−sa−1,d+sa−1,b−1
差分
矩形的
s
s
s值均价
v
v
v：
a
a
,
b
+
=
v
a_{a,b}+=v
aa,b+=v
a
c
+
1
,
b
−
=
v
a_{c+1,b}-=v
ac+1,b−=v
a
a
,
d
+
1
−
=
v
a_{a,d+1}-=v
aa,d+1−=v
s
c
+
1
,
d
+
1
+
=
v
s_{c+1,d+1}+=v
sc+1,d+1+=v
高维前缀和与SOS DP
https://zhuanlan.zhihu.com/p/651143987
https://www.cnblogs.com/KellyWLJ/p/18015746
[CF165E Compatible Numbers]
[CF383E Vowels]
树上
前缀和
s
[
u
]
s[u]
s[u]为
u
u
u到根路径上的
a
a
a值和
查询某树上路径的
a
a
a值和
分为点前缀和 和 边前缀和
差分
s
[
u
]
s[u]
s[u]为
u
u
u的子树内的
a
a
a值和
修改某树上路径的
s
s
s值
分为点差分 和 树差分
[刷题笔记]