一、 算法&数据结构

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 的子数组数目

五、参考链接

• 链接: 灵神的位运算题单