6158. 字母移位 II【差分数组模板 + 区间加减相同值单点查询不要用segTree】

分析

反正用了segTree的区间增减相同值 + 单点查询就是很悲催
segTree不是万能的
这里用diff差分数组
区间改的时候假设【x， y】
那么只需要改动diff[x]和diff[y + 1]
如果区间+，diff[x]+, diff[y + 1]-
若-则全部相反
到时候的值就是全部diff加起来到某一位

Ac code

class Solution:
    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:
        # inc_seg + query one point is dangerous
        # 区间增减相同值 + 单点查询 = use diff
        n = len(s)
        diff = [0] * (n + 1)
        for x, y, d in shifts:
            if d == 1:
                diff[x] += 1
                diff[y + 1] -= 1
            else:
                diff[x] -= 1
                diff[y + 1] += 1
        
        #print(diff)
        res = ''
        offset = 0
        for i in range(n):
            offset += diff[i]
            now = chr((ord(s[i]) - ord('a') + offset) % 26 + ord('a'))
            res += now
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

总结

差分数组入门
垃圾segTree