一、 算法&數據結構

1. 描述

LogTrick可以用來計算子段區間的可重復貢獻問題（即op(x,x) = x, 通常就是指ior、iand、gcd）信息。
通常會關注整個數組的信息，而不僅僅是某一個位置上的答案。
下文描述以或和為例。

# 	模板1
def log_trick_vs(nums: List[int], op=and_):"""獲取nums的所有子段的'與值'，返回所有值，共nlogU個。由于不計算個數，不需要計算左右邊界，因此常數低，快1/3左右---注意會直接修改原數組，可酌情拷貝使用-----"""res = set()for i, v in enumerate(nums):res.add(v)  # 在這行做你想做的事for j in range(i - 1, -1, -1):if op(nums[j], v) == nums[j]: breaknums[j] = op(nums[j], v)res.add(nums[j])  # 在這行做你想做的事return res

• 解釋上述代碼：

1. 向右遍歷nums到i時，更新前邊訪問過的位置j，在j上儲存的信息為nums[j]=op(j…i),發現這個信息是從i-1層轉移過來的，因此可以遞推。
2. 當遇到op(nums[j], v) == nums[j]時，即無法使op(j…i)超過op(j…i-1)時，可以退出，繼續向前也無法更新nums[j]了。證明，以或運算為例：
   1. 由于離i越遠，或和越大，可以證明左邊的數字一定大于等于右邊，且一定包含右邊，即nums[i]∈nums[i-1]。
   2. 若nums[i]|v==nums[i],證明nums[i]一定包含了v，那么nums[i-1]肯定也包含了v。即v∈nums[i]∈nums[i-1]。
3. 同時由于j是從i向左遍歷的，可以發現這樣可以完整無遺漏的遍歷到所有以i為右端點的子段的或和所有可能值的右半部分。而左半部分由于i無法更新到，會有i-1、i-2…或其他更新到。

# 模板2
def log_trick_v_cnt(nums: List[int], op=and_):"""獲取nums的所有子段'與值'，返回所有值的個數，共nlogU個。時間復雜度O(nlogU)"""res = defaultdict(int)dp = []  # 順序儲存 [左邊界，右邊界),值for pos, cur in enumerate(nums):for v in dp:v[2] = op(v[2], cur)dp.append([pos, pos + 1, cur])ptr = 0for v in dp[1:]:  # 雙指針向前合并去重if dp[ptr][2] != v[2]:ptr += 1dp[ptr] = velse:dp[ptr][1] = v[1]# dp = dp[: ptr + 1]del dp[ptr + 1:]for l, r, v in dp:res[v] += r - lreturn res

• 這是另一種寫法，顯式創建了每一層的dp數組，并記錄了左右邊界。
• 由于每一層只有logU種可能性，且是單調的，用了雙指針的技巧維護擴縮容。

2. 復雜度分析

1. 時間復雜度整體O(nlog₂U)；gcd的話再多一個gcd的log。證明：
   分析每個i向前能走多遠比較困難，我們分析Nums[j]，每個數字被更新多少次。
   由于每個位置被更新時一定會變大，或這個動作會保證數字變大時，至少會多一個位置的0變成1。因此每個數字至多變大log(U)次
2. 空間復雜度：如果要存所有子段或和，那共有O(nlogU)個；否則通常可以復用nums原數組，則額外空間只需要O(1)

3. 常見應用

1. （找值）枚舉所有區間子段的or、and、gcd，找最大、最小、最近值等。
2. （找段）以每個位置i為右(左)端點，不同子段與的左端點起止位置，以此也可以計算子段數量。

4. 常用優化

1. 如果只關心值信息本身，那么可以復用nums數組，原地修改，效率極高。
2. 找段時，可以用字典儲存每個信息對應的段首尾，顯式儲存以當前位置為結尾的或和這個dp數組。
3. 更新過程中，截止當前位置的左邊數字是單調的，可以二分。

二、 模板代碼

1. 特定或值的最短子數組

例題: 3097. 或值至少為 K 的最短子數組 II

• 題目要求子段的或值至少為k，直接套模板，當判斷超過k時，i-j+1就可以更新以i為右端點的答案。

class Solution:def minimumSubarrayLength(self, nums: List[int], k: int) -> int:ans = inf for i, v in enumerate(nums):if v >= k:return 1 for j in range(i-1,-1,-1):if (nums[j]|v) >= k:ans = min(ans, i-j+1)if (nums[j]|v) == nums[j]:break nums[j] |= v return ans if ans < inf else -1

2. 找特定值

鏈接: 3171. 找到按位或最接近 K 的子數組

• 本地直接問所有或值中最接近k的是幾，那么貼模板，把所有值遍歷一次就行

class Solution:def minimumDifference(self, nums: List[int], k: int) -> int:ans = inffor i, x in enumerate(nums):ans = min(ans, abs(x - k))for j in range(i - 1, -1, -1):if nums[j] | x == nums[j]:breaknums[j] |= xans = min(ans, abs(nums[j] - k))return ans

3. 找位置j的最后一次被誰更新

鏈接: 2411. 按位或最大的最小子數組長度

• 題目問以每個i為左端點，向右達到最大或的位置。
• 考慮logTrick時間復雜度的證明：每個nums[j]只會被變大logU次

class Solution:def smallestSubarrays(self, nums: List[int]) -> List[int]:n = len(nums) ans = [1]*nfor i, v in enumerate(nums):for j in range(i-1,-1,-1):             if nums[j] | v == nums[j]:break nums[j] |= v ans[j] = i-j+1           return ans

4. 問某個或和的數量

鏈接: [3209. 子數組按位與值為 K 的數目]https://leetcode.cn/problems/number-of-subarrays-with-and-value-of-k/description/)

• 貼模板2

def log_trick_v_cnt(nums: List[int], op=and_):res = defaultdict(int)dp = []  # 順序儲存 [左邊界，右邊界),值for pos, cur in enumerate(nums):for v in dp:v[2] = op(v[2], cur)dp.append([pos, pos + 1, cur])ptr = 0for v in dp[1:]:  # 雙指針向前合并去重if dp[ptr][2] != v[2]:ptr += 1dp[ptr] = velse:dp[ptr][1] = v[1]# dp = dp[: ptr + 1]del dp[ptr + 1:]  # little fasterfor l, r, v in dp:res[v] += r - lreturn res
class Solution:def countSubarrays(self, nums: List[int], k: int) -> int:res = log_trick_v_cnt(nums)return res[k]

三、其他

1. 之所以算trick，這個做法其實不太通用，應對的場景比較局限。
2. 當固定某個端點時，向一側的子段值是單調的，因此以上所有題目都可以用st表+二分解決。如果覺得logTrick不好理解，可以先嘗試本方法解決以上問題。

四、更多例題

• 2447. 最大公因數等于 K 的子數組數目

五、參考鏈接

• 鏈接: 靈神的位運算題單