企业官网建设流程全解析

LeetCode 2381 Shifting Letters II 全解：差分数组与 Fenwick 树实现字符串区间移位

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

导读

Shifting Letters II（LeetCode 2381）是一道将"字符串操作"与"区间更新"结合的经典题：给定一个字符串与若干形如[start, end, direction]的移位操作，求最终字符串。本文以仓库中的题解文档 articles/shifting-letters-ii.md 为主体骨架，完整讲解暴力法、差分数组（Sweep Line）与树状数组（Binary Indexed Tree / Fenwick Tree）三种解法，并给出 Python、Java、C++、JavaScript、C#、Go、Kotlin、Swift、Rust 九种语言的可用代码。读完本文，你将掌握"区间批量更新 + 单点取值"的通用建模方式，并能顺手迁移到差分数组、前缀和、Fenwick 树等同类问题。

一、前置知识（Prerequisites）

在动手实现之前，需要具备以下三项基础能力，它们分别对应三种解法的核心支撑：

• 数组与字符串操作：能够使用 ASCII 值与模运算在字符数组上迭代和修改。本题中字符'a'对应0、'z'对应25，移位本质就是在0..25的环上做加减。
• 前缀和 / 差分数组（Difference Array）：扫描线（Sweep Line）技巧通过差分数组高效完成区间更新，这是最优解的核心。仓库中 articles/car-pooling.md 对"区间增减事件 + 前缀累加"的同款套路有独立讲解，可对照学习。
• 模运算：字符越过'z'或低于'a'时需要环绕，而多数语言对负数取模会得到负数结果（例如某些语言中-1 % 26 == -1），因此必须掌握"先加 26 再取模"的规范化写法。

二、问题建模与输入约定

shifts中的每个操作是三元组[l, r, d]：

注意区间是闭区间[l, r]，这是后续"差分数组合并在r + 1处取消"这一 off-by-one 细节的根源。

三、解法一：暴力法（Brute Force）

3.1 直觉

最直接的做法是逐个应用每次移位操作：对于每个[l, r, d]，遍历区间内每个字符并加 1 或减 1，字符环绕字母表时使用模 26 运算。这种方式实现简单，但因为多个移位区间可能相互重叠，同一字符会被反复处理，整体较慢。

3.2 算法步骤

1. 将字符串转换为整数数组（'a'对应0，'z'对应25）。
2. 对每个移位[l, r, d]：
   • 遍历下标l到r；
   • 方向为前移则+1，后移则-1；
   • 对结果执行模 26 处理环绕。
3. 将整数数组转换回字符。
4. 返回结果字符串。

3.3 多语言实现

class Solution: def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str: s = [ord(c) - ord('a') for c in s] for l, r, d in shifts: for i in range(l, r + 1): s[i] += 1 if d else -1 s[i] %= 26 s = [chr(ord('a') + c) for c in s] return "".join(s)

class Solution { public String shiftingLetters(String s, int[][] shifts) { char[] arr = s.toCharArray(); int[] letters = new int[arr.length]; for (int i = 0; i < arr.length; i++) { letters[i] = arr[i] - 'a'; } for (int[] shift : shifts) { int l = shift[0], r = shift[1], d = shift[2]; for (int i = l; i <= r; i++) { letters[i] = (letters[i] + (d == 1 ? 1 : -1) + 26) % 26; } } for (int i = 0; i < arr.length; i++) { arr[i] = (char) (letters[i] + 'a'); } return new String(arr); } }

class Solution { public: string shiftingLetters(string s, vector<vector<int>>& shifts) { vector<int> letters(s.size()); for (int i = 0; i < s.size(); i++) { letters[i] = s[i] - 'a'; } for (const auto& shift : shifts) { int l = shift[0], r = shift[1], d = shift[2]; for (int i = l; i <= r; i++) { letters[i] = (letters[i] + (d == 1 ? 1 : -1) + 26) % 26; } } for (int i = 0; i < s.size(); i++) { s[i] = letters[i] + 'a'; } return s; } };

class Solution { /** * @param {string} s * @param {number[][]} shifts * @return {string} */ shiftingLetters(s, shifts) { let arr = Array.from(s).map((c) => c.charCodeAt(0) - 97); for (const [l, r, d] of shifts) { for (let i = l; i <= r; i++) { arr[i] = (arr[i] + (d === 1 ? 1 : -1) + 26) % 26; } } return arr.map((c) => String.fromCharCode(c + 97)).join(''); } }

public class Solution { public string ShiftingLetters(string s, int[][] shifts) { char[] arr = s.ToCharArray(); int[] letters = new int[arr.Length]; for (int i = 0; i < arr.Length; i++) { letters[i] = arr[i] - 'a'; } foreach (int[] shift in shifts) { int l = shift[0], r = shift[1], d = shift[2]; for (int i = l; i <= r; i++) { letters[i] = (letters[i] + (d == 1 ? 1 : -1) + 26) % 26; } } for (int i = 0; i < arr.Length; i++) { arr[i] = (char)(letters[i] + 'a'); } return new string(arr); } }

func shiftingLetters(s string, shifts [][]int) string { letters := make([]int, len(s)) for i := 0; i < len(s); i++ { letters[i] = int(s[i] - 'a') } for _, shift := range shifts { l, r, d := shift[0], shift[1], shift[2] for i := l; i <= r; i++ { if d == 1 { letters[i] = (letters[i] + 1 + 26) % 26 } else { letters[i] = (letters[i] - 1 + 26) % 26 } } } result := make([]byte, len(s)) for i := 0; i < len(s); i++ { result[i] = byte(letters[i] + 'a') } return string(result) }

class Solution { fun shiftingLetters(s: String, shifts: Array<IntArray>): String { val arr = s.map { it - 'a' }.toIntArray() for ((l, r, d) in shifts) { for (i in l..r) { arr[i] = (arr[i] + (if (d == 1) 1 else -1) + 26) % 26 } } return arr.map { ('a' + it) }.joinToString("") } }

class Solution { func shiftingLetters(_ s: String, _ shifts: [[Int]]) -> String { var arr = s.map { Int($0.asciiValue! - Character("a").asciiValue!) } for shift in shifts { let l = shift[0], r = shift[1], d = shift[2] for i in l...r { arr[i] = (arr[i] + (d == 1 ? 1 : -1) + 26) % 26 } } return String(arr.map { Character(UnicodeScalar($0 + Int(Character("a").asciiValue!))!) }) } }

impl Solution { pub fn shifting_letters(s: String, shifts: Vec<Vec<i32>>) -> String { let mut letters: Vec<i32> = s.bytes().map(|b| (b - b'a') as i32).collect(); for shift in &shifts { let (l, r, d) = (shift[0] as usize, shift[1] as usize, shift[2]); for i in l..=r { letters[i] = (letters[i] + if d == 1 { 1 } else { -1 } + 26) % 26; } } letters.iter().map(|&c| (c as u8 + b'a') as char).collect() } }

3.4 复杂度分析

• 时间复杂度：$O(n \times m)$
• 空间复杂度：$O(n)$

其中 $n$ 为字符串s的长度，$m$ 为shifts数组的大小。每次移位最多遍历整个字符串，最坏情况下 $m$ 次操作全部覆盖全长区间。

四、解法二：扫描线 / 差分数组（Sweep Line Algorithm）

4.1 直觉

与其逐条应用移位，不如用差分数组（Difference Array）标记移位的起止，再通过一次从左到右的前缀累加得到每个位置上的净移位量。

差分数组的核心思想是：对区间[l, r]的更新，只需在l处加val、在r + 1处减val；随后对差分数组求前缀和，每个位置便自动累积了所有重叠区间的总贡献。仓库中 articles/car-pooling.md 的"上车/下车人数差分"正是同一技术的另一处应用，可以交叉验证这一建模方式。

4.2 算法步骤

1. 创建大小为n + 1的差分数组prefix_diff，初始化为 0。
2. 对每个移位[l, r, d]：
   • 在l处加上+1或-1（依据方向）；
   • 在r + 1处减去同样的值（区间结束的取消标记）。
3. 遍历字符串并计算运行和：
   • 维护累计变量diff；
   • 对每个下标把净移位量叠加到字符上；
   • 用模 26 处理环绕。
4. 返回结果字符串。

这里必须强调：取消标记放在r + 1而非r。放在r会导致区间最后一个字符丢失移位，这正是差分数组最容易踩的 off-by-one 陷阱。

4.3 多语言实现

class Solution: def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str: prefix_diff = [0] * (len(s) + 1) for left, right, d in shifts: val = 1 if d == 1 else -1 prefix_diff[left] += val prefix_diff[right + 1] -= val diff = 0 res = [ord(c) - ord("a") for c in s] for i in range(len(s)): diff += prefix_diff[i] res[i] = (diff + res[i] + 26) % 26 s = [chr(ord("a") + n) for n in res] return "".join(s)

class Solution { public String shiftingLetters(String s, int[][] shifts) { int n = s.length(); int[] prefix_diff = new int[n + 1]; for (int[] shift : shifts) { int left = shift[0], right = shift[1], d = shift[2]; int val = d == 1 ? 1 : -1; prefix_diff[left] += val; prefix_diff[right + 1] -= val; } int[] res = new int[n]; for (int i = 0; i < n; i++) { res[i] = s.charAt(i) - 'a'; } int diff = 0; for (int i = 0; i < n; i++) { diff += prefix_diff[i]; res[i] = (res[i] + diff % 26 + 26) % 26; } StringBuilder sb = new StringBuilder(); for (int i = 0; i < n; i++) { sb.append((char) ('a' + res[i])); } return sb.toString(); } }

class Solution { public: string shiftingLetters(string s, vector<vector<int>>& shifts) { int n = s.size(); vector<int> prefix_diff(n + 1, 0); for (auto& shift : shifts) { int left = shift[0], right = shift[1], d = shift[2]; int val = d == 1 ? 1 : -1; prefix_diff[left] += val; prefix_diff[right + 1] -= val; } int diff = 0; vector<int> res(n); for (int i = 0; i < n; ++i) { res[i] = s[i] - 'a'; } for (int i = 0; i < n; ++i) { diff += prefix_diff[i]; res[i] = (diff % 26 + res[i] + 26) % 26; } for (int i = 0; i < n; ++i) { s[i] = 'a' + res[i]; } return s; } };

class Solution { /** * @param {string} s * @param {number[][]} shifts * @return {string} */ shiftingLetters(s, shifts) { const n = s.length; const prefix_diff = Array(n + 1).fill(0); for (const [left, right, d] of shifts) { const val = d === 1 ? 1 : -1; prefix_diff[left] += val; prefix_diff[right + 1] -= val; } let diff = 0; const res = Array.from(s).map( (c) => c.charCodeAt(0) - 'a'.charCodeAt(0), ); for (let i = 0; i < n; i++) { diff += prefix_diff[i]; res[i] = ((diff % 26) + res[i] + 26) % 26; } return res .map((x) => String.fromCharCode('a'.charCodeAt(0) + x)) .join(''); } }

public class Solution { public string ShiftingLetters(string s, int[][] shifts) { int n = s.Length; int[] prefix_diff = new int[n + 1]; foreach (int[] shift in shifts) { int left = shift[0], right = shift[1], d = shift[2]; int val = d == 1 ? 1 : -1; prefix_diff[left] += val; prefix_diff[right + 1] -= val; } int[] res = new int[n]; for (int i = 0; i < n; i++) { res[i] = s[i] - 'a'; } int diff = 0; for (int i = 0; i < n; i++) { diff += prefix_diff[i]; res[i] = (res[i] + diff % 26 + 26) % 26; } char[] result = new char[n]; for (int i = 0; i < n; i++) { result[i] = (char)('a' + res[i]); } return new string(result); } }

func shiftingLetters(s string, shifts [][]int) string { n := len(s) prefixDiff := make([]int, n+1) for _, shift := range shifts { left, right, d := shift[0], shift[1], shift[2] val := 1 if d == 0 { val = -1 } prefixDiff[left] += val prefixDiff[right+1] -= val } diff := 0 res := make([]int, n) for i := 0; i < n; i++ { res[i] = int(s[i] - 'a') } for i := 0; i < n; i++ { diff += prefixDiff[i] res[i] = ((diff%26 + res[i]) + 26) % 26 } result := make([]byte, n) for i := 0; i < n; i++ { result[i] = byte(res[i] + 'a') } return string(result) }

class Solution { fun shiftingLetters(s: String, shifts: Array<IntArray>): String { val n = s.length val prefixDiff = IntArray(n + 1) for ((left, right, d) in shifts) { val value = if (d == 1) 1 else -1 prefixDiff[left] += value prefixDiff[right + 1] -= value } var diff = 0 val res = s.map { it - 'a' }.toIntArray() for (i in 0 until n) { diff += prefixDiff[i] res[i] = ((diff % 26 + res[i]) + 26) % 26 } return res.map { ('a' + it) }.joinToString("") } }

class Solution { func shiftingLetters(_ s: String, _ shifts: [[Int]]) -> String { let n = s.count var prefixDiff = Int for shift in shifts { let left = shift[0], right = shift[1], d = shift[2] let val = d == 1 ? 1 : -1 prefixDiff[left] += val prefixDiff[right + 1] -= val } var diff = 0 var res = s.map { Int($0.asciiValue! - Character("a").asciiValue!) } for i in 0..<n { diff += prefixDiff[i] res[i] = ((diff % 26 + res[i]) + 26) % 26 } return String(res.map { Character(UnicodeScalar($0 + Int(Character("a").asciiValue!))!) }) } }

impl Solution { pub fn shifting_letters(s: String, shifts: Vec<Vec<i32>>) -> String { let n = s.len(); let mut prefix_diff = vec![0i32; n + 1]; for shift in &shifts { let (left, right, d) = (shift[0] as usize, shift[1] as usize, shift[2]); let val = if d == 1 { 1 } else { -1 }; prefix_diff[left] += val; prefix_diff[right + 1] -= val; } let mut res: Vec<i32> = s.bytes().map(|b| (b - b'a') as i32).collect(); let mut diff = 0i32; for i in 0..n { diff += prefix_diff[i]; res[i] = ((res[i] + diff % 26) + 26) % 26; } res.iter().map(|&c| (c as u8 + b'a') as char).collect() } }

4.4 复杂度分析

• 时间复杂度：$O(n + m)$
• 空间复杂度：$O(n)$

其中 $n$ 为字符串s的长度，$m$ 为shifts数组的大小。每次移位只做两次 $O(1)$ 的差分标记，最后线性扫描一次完成前缀和与字符转换，是本题的标准最优解。

五、解法三：树状数组 / 二叉索引树（Binary Indexed Tree, Fenwick Tree）

5.1 直觉

树状数组（BIT）天然擅长"区间更新 + 单点查询"：对区间[l, r]统一加delta时，只需在l处update(l, delta)、在r + 1处update(r + 1, -delta)；查询某点时取其前缀和即可得到该点累计的净增量。这与差分数组在数学上是同一套思路，但 BIT 用树形结构与index & -index位运算把单次更新与查询压到 $O(\log n)$。

当移位需要动态追加，或在扫描过程中需要随时查询中间某个位置的当前移位量时，BIT 比一次性构造的差分数组更灵活——不需要在开头就拿到全部操作，也不需要为"提前读取某个前缀和"而额外维护运行变量。

仓库中的 articles/range-sum-query-mutable.md 对 Fenwick Tree 的index & -index位运算机制与点更新/区间查询模板有完整说明，可结合本篇的"区间更新 + 点查询"用法对照掌握。

5.2 算法步骤

1. 初始化大小为n + 2的 BIT。
2. 对每个移位[l, r, d]：
   • 令delta为+1（前移）或-1（后移）；
   • 执行update(l, delta)与update(r + 1, -delta)完成区间更新。
3. 对字符串中的每个字符：
   • 查询 BIT 得到该位置的累计移位量；
   • 用模 26 规范化后应用到字符；
   • 拼装结果字符。
4. 返回结果字符串。

说明：BIT 内部采用 1-based 索引，因此对外暴露的 0-based 下标在update与prefix_sum入口处先+1；底层数组分配n + 2是为了让r + 1 == n时取消标记仍能落在有效下标内。

5.3 多语言实现

class BIT: def __init__(self, size): self.n = size + 2 self.tree = [0] * self.n def update(self, index, delta): index += 1 while index < self.n: self.tree[index] += delta index += index & -index def prefix_sum(self, index): index += 1 total = 0 while index > 0: total += self.tree[index] index -= index & -index return total def range_update(self, left, right, delta): self.update(left, delta) self.update(right + 1, -delta) class Solution: def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str: n = len(s) bit = BIT(n) for left, right, d in shifts: delta = 1 if d == 1 else -1 bit.range_update(left, right, delta) res = [] for i in range(n): shift = bit.prefix_sum(i) % 26 code = (ord(s[i]) - ord('a') + shift + 26) % 26 res.append(chr(ord('a') + code)) return ''.join(res)

class BIT { int[] tree; int n; public BIT(int size) { n = size + 2; tree = new int[n]; } public void update(int index, int delta) { index++; while (index < n) { tree[index] += delta; index += index & -index; } } public int prefixSum(int index) { index++; int sum = 0; while (index > 0) { sum += tree[index]; index -= index & -index; } return sum; } public void rangeUpdate(int left, int right, int delta) { update(left, delta); update(right + 1, -delta); } } public class Solution { public String shiftingLetters(String s, int[][] shifts) { int n = s.length(); BIT bit = new BIT(n); for (int[] shift : shifts) { int left = shift[0], right = shift[1], d = shift[2]; int delta = d == 1 ? 1 : -1; bit.rangeUpdate(left, right, delta); } StringBuilder res = new StringBuilder(); for (int i = 0; i < n; i++) { int shift = bit.prefixSum(i) % 26; int code = (s.charAt(i) - 'a' + shift + 26) % 26; res.append((char) ('a' + code)); } return res.toString(); } }

class BIT { vector<int> tree; int n; public: BIT(int size) { n = size + 2; tree.assign(n, 0); } void update(int index, int delta) { index++; while (index < n) { tree[index] += delta; index += index & -index; } } int prefixSum(int index) { index++; int sum = 0; while (index > 0) { sum += tree[index]; index -= index & -index; } return sum; } void rangeUpdate(int left, int right, int delta) { update(left, delta); update(right + 1, -delta); } }; class Solution { public: string shiftingLetters(string s, vector<vector<int>>& shifts) { int n = s.size(); BIT bit(n); for (auto& shift : shifts) { int left = shift[0], right = shift[1], d = shift[2]; int delta = d == 1 ? 1 : -1; bit.rangeUpdate(left, right, delta); } string res; for (int i = 0; i < n; i++) { int shift = bit.prefixSum(i) % 26; int code = (s[i] - 'a' + shift + 26) % 26; res += char('a' + code); } return res; } };

class BIT { /** * @constructor * @param {number} size */ constructor(size) { this.n = size + 2; this.tree = new Array(this.n).fill(0); } /** * @param {number} index * @param {number} delta * @return {void} */ update(index, delta) { index++; while (index < this.n) { this.tree[index] += delta; index += index & -index; } } /** * @param {number} index * @return {number} */ prefixSum(index) { index++; let sum = 0; while (index > 0) { sum += this.tree[index]; index -= index & -index; } return sum; } /** * @param {number} left * @param {number} right * @param {number} delta * @return {void} */ rangeUpdate(left, right, delta) { this.update(left, delta); this.update(right + 1, -delta); } } class Solution { /** * @param {string} s * @param {number[][]} shifts * @return {string} */ shiftingLetters(s, shifts) { const n = s.length; const bit = new BIT(n); for (const [left, right, d] of shifts) { const delta = d === 1 ? 1 : -1; bit.rangeUpdate(left, right, delta); } let res = ''; for (let i = 0; i < n; i++) { const shift = bit.prefixSum(i) % 26; const code = (s.charCodeAt(i) - 97 + shift + 26) % 26; res += String.fromCharCode(97 + code); } return res; } }

public class BIT { private int[] tree; private int n; public BIT(int size) { n = size + 2; tree = new int[n]; } public void Update(int index, int delta) { index++; while (index < n) { tree[index] += delta; index += index & -index; } } public int PrefixSum(int index) { index++; int sum = 0; while (index > 0) { sum += tree[index]; index -= index & -index; } return sum; } public void RangeUpdate(int left, int right, int delta) { Update(left, delta); Update(right + 1, -delta); } } public class Solution { public string ShiftingLetters(string s, int[][] shifts) { int n = s.Length; BIT bit = new BIT(n); foreach (var shift in shifts) { int left = shift[0], right = shift[1], d = shift[2]; int delta = d == 1 ? 1 : -1; bit.RangeUpdate(left, right, delta); } char[] res = new char[n]; for (int i = 0; i < n; i++) { int sh = bit.PrefixSum(i) % 26; int code = (s[i] - 'a' + sh + 26) % 26; res[i] = (char)('a' + code); } return new string(res); } }

type BIT struct { tree []int n int } func NewBIT(size int) *BIT { n := size + 2 return &BIT{ tree: make([]int, n), n: n, } } func (b *BIT) Update(index, delta int) { index++ for index < b.n { b.tree[index] += delta index += index & -index } } func (b *BIT) PrefixSum(index int) int { index++ sum := 0 for index > 0 { sum += b.tree[index] index -= index & -index } return sum } func (b *BIT) RangeUpdate(left, right, delta int) { b.Update(left, delta) b.Update(right+1, -delta) } func shiftingLetters(s string, shifts [][]int) string { n := len(s) bit := NewBIT(n) for _, shift := range shifts { left, right, d := shift[0], shift[1], shift[2] delta := 1 if d == 0 { delta = -1 } bit.RangeUpdate(left, right, delta) } res := make([]byte, n) for i := 0; i < n; i++ { sh := bit.PrefixSum(i) % 26 code := ((int(s[i]-'a') + sh) % 26 + 26) % 26 res[i] = byte('a' + code) } return string(res) }

class BIT(size: Int) { private val n = size + 2 private val tree = IntArray(n) fun update(index: Int, delta: Int) { var i = index + 1 while (i < n) { tree[i] += delta i += i and -i } } fun prefixSum(index: Int): Int { var i = index + 1 var sum = 0 while (i > 0) { sum += tree[i] i -= i and -i } return sum } fun rangeUpdate(left: Int, right: Int, delta: Int) { update(left, delta) update(right + 1, -delta) } } class Solution { fun shiftingLetters(s: String, shifts: Array<IntArray>): String { val n = s.length val bit = BIT(n) for ((left, right, d) in shifts) { val delta = if (d == 1) 1 else -1 bit.rangeUpdate(left, right, delta) } val res = StringBuilder() for (i in 0 until n) { val sh = bit.prefixSum(i) % 26 val code = ((s[i] - 'a' + sh) % 26 + 26) % 26 res.append('a' + code) } return res.toString() } }

class BIT { private var tree: [Int] private var n: Int init(_ size: Int) { n = size + 2 tree = Int } func update(_ index: Int, _ delta: Int) { var i = index + 1 while i < n { tree[i] += delta i += i & -i } } func prefixSum(_ index: Int) -> Int { var i = index + 1 var sum = 0 while i > 0 { sum += tree[i] i -= i & -i } return sum } func rangeUpdate(_ left: Int, _ right: Int, _ delta: Int) { update(left, delta) update(right + 1, -delta) } } class Solution { func shiftingLetters(_ s: String, _ shifts: [[Int]]) -> String { let n = s.count let bit = BIT(n) let chars = Array(s) for shift in shifts { let left = shift[0], right = shift[1], d = shift[2] let delta = d == 1 ? 1 : -1 bit.rangeUpdate(left, right, delta) } var res = "" for i in 0..<n { let sh = bit.prefixSum(i) % 26 let charVal = Int(chars[i].asciiValue! - Character("a").asciiValue!) let code = ((charVal + sh) % 26 + 26) % 26 res += String(Character(UnicodeScalar(code + Int(Character("a").asciiValue!))!)) } return res } }

struct BIT { tree: Vec<i32>, n: usize, } impl BIT { fn new(size: usize) -> Self { let n = size + 2; BIT { tree: vec![0; n], n } } fn update(&mut self, index: usize, delta: i32) { let mut i = index + 1; while i < self.n { self.tree[i] += delta; i += i & i.wrapping_neg(); } } fn prefix_sum(&self, index: usize) -> i32 { let mut i = index + 1; let mut sum = 0; while i > 0 { sum += self.tree[i]; i -= i & i.wrapping_neg(); } sum } fn range_update(&mut self, left: usize, right: usize, delta: i32) { self.update(left, delta); self.update(right + 1, -delta); } } impl Solution { pub fn shifting_letters(s: String, shifts: Vec<Vec<i32>>) -> String { let n = s.len(); let mut bit = BIT::new(n); for shift in &shifts { let (left, right, d) = (shift[0] as usize, shift[1] as usize, shift[2]); let delta = if d == 1 { 1 } else { -1 }; bit.range_update(left, right, delta); } let bytes = s.as_bytes(); let mut res = String::with_capacity(n); for i in 0..n { let sh = bit.prefix_sum(i) % 26; let code = ((bytes[i] as i32 - b'a' as i32 + sh) % 26 + 26) % 26; res.push((code as u8 + b'a') as char); } res } }

5.4 复杂度分析

• 时间复杂度：$O((m + n) \times \log n)$
• 空间复杂度：$O(n)$

其中 $n$ 为字符串s的长度，$m$ 为shifts数组的大小。每次区间更新是两次 $O(\log n)$ 的单点更新，每个字符查询一次前缀和也是 $O(\log n)$。

六、常见陷阱（Common Pitfalls）

6.1 忘记处理负数取模

向后移位时，中间结果在取模前可能变成负数。而不少编程语言对负数取模会返回负数（例如-1 % 26 == -1）。因此必须先加 26 再取模，保证结果落在[0, 25]：

((shift + char) % 26 + 26) % 26

原文档中九种语言的实现都采用了(x + 26) % 26或(x % 26 + 26) % 26的写法，正是为了规避这一语言层面的差异。

6.2 差分数组的 Off-by-One 错误

使用扫描线 / 差分数组时，取消标记必须放在r + 1而不是r。若把取消放在r，区间最后一个字符将得不到移位。牢记：prefix_diff[right + 1] -= val才能保证移位完整作用于从left到right（含两端）的所有下标。

6.3 忽略累积移位量过大的问题

大量重叠移位会使累计值（正负都可能）变得很大。只在全部累加结束后取一次模是正确做法；有些实现试图在每次移位后立即规范化，反而容易引入隐蔽 bug。务必在累加完所有前缀值之后再做最终的模运算。

七、三种解法对比与选型建议

• 面试与竞赛首选差分数组：单次 $O(n + m)$，实现最简洁，也最契合"区间批量更新 + 单点取值"的经典建模。
• Fenwick Tree 的价值在于动态性：当移位操作不是一次性给出，而是逐步插入、且需要穿插查询某个位置的当前移位量时，BIT 无需重建即可支持 $O(\log n)$ 的点查询。仓库中 articles/range-sum-query-mutable.md 展示了 BIT 在"点更新 + 区间求和"方向的模板，与本题的"区间更新 + 点查询"正好构成互补的两面。
• 暴力法用于校验：在小规模样例上，暴力法可作为差分/BIT 实现的对照基准，快速定位 off-by-one 与取模错误。

本文完整实现与讲解均收录于 articles/shifting-letters-ii.md；同仓库还提供了 articles/car-pooling.md（差分数组另一应用）、articles/range-sum-query-mutable.md（Fenwick Tree 模板）等可交叉学习的题解文档，各语言源码则分布在python/、java/、cpp/、javascript/、typescript/、go/、rust/、kotlin/、swift/、csharp/等目录下，可自行对照查阅。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode