差分是一种和前缀和相对的策略，可以当做是 {{c1 求和}} 的逆运算

求差分数据的公式 #card

• $b_{i}= \begin{cases}a_{i}-a_{i-1} & i \in[2, n] \ a_{1} & i=1\end{cases}$

性质

• ai 是 bi 的前缀和
• 计算前缀和 #card
  • $\text { sum }=\sum_{i=1}^{n} a_{i}=\sum_{i=1}^{n} \sum_{j=1}^{i} b_{j}=\sum_{i}^{n}(n-i+1) b_{i}$
• 区间序列 [l,r] 加上一个数 k #card
  • $b_{l} \leftarrow b_{l}+k, b_{r+1} \leftarrow b_{r+1}-k$

例题

• 798. 得分最高的最小轮调 - 力扣（LeetCode） (leetcode-cn.com)

和树状数组区别 #card

• 树状数组：单点更新，区间查询
• 差分数组：区间更新，单点查询

$dp[i][j]=max(dp[i][j], dp[i][k]+dp[k+1][j]+cost[i][j])$

从小到大枚举区间的长度

确定 i,j，枚举中间的点，由于先枚举的长度，i和j之间更小的区间都已经被计算过。

使用场景

• 数组会被分割成若干段，且每一段判断/处理逻辑是一样的。

好处

• 无序判空
• 无需在循环结束后再补上最后一段区间的逻辑

1
2
3
4
5
6
7

i, n = 0, len(nums)
while i < n:
    start = i
    while i < n and ...:
        i += 1
    # 从 start 到 i-1 是一段
    # 下一段从 i 开始，无需 i+=1

将在原串中加入特殊字符,比如#组成一个新的字符串,这样可以把所有奇数或偶数的字符串都变成奇数长度的字符串. 例如abba可以转化成$#a#b#b#a

用一个辅助数组P[i],代表以S[i]为中心的最长回文串向左或向右扩展的长度.最后max(P[i]-1)为最长回文串的长度

• 当 mx - i > P[j] 的时候，以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中，由于 i 和 j 对称，以S[i]为中心的回文子串必然包含在以S[id]为中心的回文子串中，所以必有 P[i] = P[j]，见下图。
• 
  当 P[j] > mx - i 的时候，以S[j]为中心的回文子串不完全包含于以S[id]为中心的回文子串中，但是基于对称性可知，下图中两个绿框所包围的部分是相同的，也就是说以S[i]为中心的回文子串，其向右至少会扩张到mx的位置，也就是说 P[i] >= mx - i。至于mx之后的部分是否对称，就只能一个一个匹配了。
  
• 对于 mx <= i 的情况，无法对 P[i]做更多的假设，只能P[i] = 1，然后再去匹配了