差分

https://leetcode.cn/problems/shifting-letters-ii/

 1 class Solution {
 2 public:
 3     string shiftingLetters(string s, vector<vector<int>>& shifts) {
 4         int n = s.size();
 5         vector<int> f(n + 1);
 6         /* 差分数组 */
 7         for (auto &shift : shifts) {
 8             int x = shift[2] * 2 - 1;
 9             f[shift[0]]     += x;
10             f[shift[1] + 1] -= x;
11         }
12 
13         int sum = 0;
14         string ans;
15         for (int i = 0; i < n; i++) { /* 前缀和求出最终的字符 */
16             sum += f[i];
17             int d = ((s[i] - 'a' + sum) % 26 + 26) % 26;
18             ans.push_back(d + 'a');
19         }
20         return ans;
21     }
22 };