多次区间字符移位为什么用差分数组？如何处理循环取模？

简化版

多次区间字符移位属于区间批量加减，适合用差分数组。

对每个操作 [l, r, dir]，如果向后移就给区间加 1，向前移就加 -1。

最后对差分数组求前缀和，得到每个位置的总移位量，再对 26 取模更新字符。

详细版

如果每个操作都逐个修改区间字符，最坏复杂度是 O(qn)。

差分数组能把一次区间更新变成两个端点操作：

diff[l] += delta
diff[r + 1] -= delta

其中 delta = 1 表示后移，delta = -1 表示前移。

所有操作处理完后，扫描字符串并累加 shift += diff[i]，当前位置总偏移是 shift。由于可能为负数，要写成：

((idx + shift) % 26 + 26) % 26

这样能正确处理负向循环。

完整版教学

一、为什么这是差分数组题

题目给很多次操作，每次都对一个连续区间内的字符整体移动。连续区间、批量加减、最后统一得到结果，这是差分数组的典型信号。差分数组不立即更新每个位置，而是在区间边界记录“从这里开始变化”和“从这里结束变化”。

记忆钩子：区间批量加，端点打标记，最后前缀还原。

二、端点标记为什么有效

如果对 [l, r] 加 delta，我们在 diff[l] += delta，表示从 l 开始多一个影响；在 diff[r+1] -= delta，表示过了 r 之后这个影响结束。最后扫描求前缀和时，l 到 r 之间都会累加到 delta，r+1 后影响被抵消。

操作	diff 变化	含义
区间开始	`diff[l] += delta`	影响开始生效
区间结束后	`diff[r+1] -= delta`	影响停止生效
最终扫描	累加 diff	得到每位总偏移

这和普通差分数组的区间加完全一致。

三、带数字推演

字符串长度 5，操作 [1,3,+1] 和 [2,4,-1]。

初始 diff: [0,0,0,0,0,0]
[1,3]+1: [0,1,0,0,-1,0]
[2,4]-1: [0,1,-1,0,-1,1]
前缀 shift: [0,1,0,0,-1]

所以第 1 位后移 1，第 2、3 位净变化 0，第 4 位前移 1。

四、取模为什么要处理负数

字符移动是环形的，'a' 前移 1 应该变成 'z'。在 JavaScript 中，负数 % 26 仍然可能是负数，例如 -1 % 26 = -1。所以需要把结果拉回 [0,25]：

const next = ((idx + shift) % 26 + 26) % 26

这条公式先取模，再加 26 修正负数，最后再取一次模保证范围。

五、代码模板

实现如下：

function shiftingLetters(s, shifts) {
  const n = s.length
  const diff = new Array(n + 1).fill(0)
  for (const [l, r, dir] of shifts) {
    const delta = dir === 1 ? 1 : -1
    diff[l] += delta
    diff[r + 1] -= delta
  }
  const chars = s.split('')
  let shift = 0
  for (let i = 0; i < n; i++) {
    shift += diff[i]
    const idx = chars[i].charCodeAt(0) - 97
    const next = ((idx + shift) % 26 + 26) % 26
    chars[i] = String.fromCharCode(97 + next)
  }
  return chars.join('')
}

diff 长度开到 n + 1，这样 r + 1 等于 n 时也能安全打结束标记。

六、常见误区与追问

误区：每个操作都逐字符修改。 操作多、区间长时会退化成 O(qn)。
误区：diff 只开 n 长度。 当 r = n-1 时，r+1 会越界；开 n+1 更统一。
误区：负数取模直接用 % 26。 JavaScript 负模仍可能为负，字符会算错。
追问：为什么最后才更新字符？ 差分数组累积的是所有操作的净影响，最后统一应用最省。
追问：如果字符集不是 26 个字母怎么办？ 把模数从 26 换成字符集大小，并调整编码映射。

这些点都来自“差分记录变化，不记录结果”的思想。

七、加强记忆

区间字符移位记成“操作打端点，扫描算净移位，字符按 26 环绕”。向后移是 +1，向前移是 -1；diff[l] 开始影响，diff[r+1] 结束影响。最后前缀累加得到每个位置的总偏移，负数取模要用双取模修正。

简化版

详细版