Logtrick 是在时间复杂度为 O(n2)O(n^2) 计算子数组问题的基础上，利用 |,&,lcm,gcd 等性质优化的一种算法。 通常用于求 子数组 经过一些操作 (gcd,lcm,&,|) 后的 max、 min 或者计数问题。

本文将分为两大部分讲解 LogTrick 的理解：

  • 子数组经过一些操作后的最值问题
  • 子数组经过一些操作后的计数问题

最值问题

OR 运算 - 最值问题

🟥 3171. 找到按位或最接近 K 的子数组 - 力扣（LeetCode）

给你一个数组 nums 和一个整数 k 。你需要找到 nums 的一个子数组，满足子数组中所有元素按位或运算 OR 的值与 k 的 绝对差 尽可能 小 。换言之，你需要选择一个子数组 nums[l..r] 满足 |k - (nums[l] OR nums[l + 1] ... OR nums[r])| 最小。

请你返回 最小 的绝对差值。

子数组 是数组中连续的 非空 元素序列。

限制：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= 10^9

从暴力方法开始讲起

我们可以想到一个 O(n2)O(n^2) 的暴力算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 暴力算法，会超时
class Solution {
    public int minimumDifference(int[] nums, int k) {
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int x = nums[i];
            ans = Math.min(ans, Math.abs(x - k)); // 单个元素也算子数组
            for (int j = i - 1; j >= 0; j--) {
                nums[j] |= x; // 现在 nums[j] = 原数组 nums[j] 到 nums[i] 的 OR
                ans = Math.min(ans, Math.abs(nums[j] - k));
            }
        }
        return ans;
    }
}

方法的要点在于把子数组相或的结果存储在 nums 中。

image.png

复杂度分析：

  • 时间复杂度： O(n2)O(n^2)
  • 空间复杂度：O(1)O(1)。

Trick!

为了充分利用 OR 的性质，我们还可以对内层循环进行优化。

内层循环 j 在递减时，如果 x 和当前 nums[j] 相或不再发生变化，那么和 nums[j-1]、nums[j-2] … nums[0] 相或也不会发生变化。这时我们可以跳出循环了。

image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int minimumDifference(int[] nums, int k) {
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int x = nums[i];
            ans = Math.min(ans, Math.abs(x - k));
            // 变化点：增加循环的约束条件
            for (int j = i - 1; j >= 0 && (nums[j] | x) != nums[j]; j--) {
                nums[j] |= x;
                ans = Math.min(ans, Math.abs(nums[j] - k));
            }
        }
        return ans;
    }
}

当 j 在递减时，x 能让当前 nums[j] 的一些比特位从 0 变为 1，如果不能就会退出内层循环。x 最大值限制为 10^9，即 x 最多有 29 个比特位，也就是说，x 最多能进行 29 次内部循环（第二重循环）。因此在本题中，内部循环的时间复杂度将是一个常数。

复杂度分析：

  • 时间复杂度：O(nlog⁡U)O(n\log U)，其中 n 是 nums 的长度，U=max⁡(nums)U=\max(nums)。
  • 空间复杂度：O(1)O(1)。

这种方法之所以被称为 LogTrick ，是因为它巧妙地利用了 OR 运算的性质，并且其时间复杂度与数字的位数（logarithm of the number）相关。

相关题目：

AND 运算最值问题

🟥 1521. 找到最接近目标值的函数值 - 力扣（LeetCode）

image.png
Winston 构造了一个如上所示的函数 func 。他有一个整数数组 arr 和一个整数 target ，他想找到让 |func(arr, l, r) - target| 最小的 l 和 r 。

请你返回 |func(arr, l, r) - target| 的最小值。

请注意， func 的输入参数 l 和 r 需要满足 0 <= l, r < arr.length 。

参考答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int closestToTarget(int[] arr, int target) {
        int len = arr.length;
        int min = Integer.MAX_VALUE;
        for(int i=0;i<len;i++){
            int x = arr[i];
            min = Math.min(Math.abs(x-target),min);
            for(int j=i-1;j>=0&&(arr[j]&x)!=arr[j];j--){
                arr[j]&=x;
                min = Math.min(Math.abs(arr[j]-target),min);
            }
        }
        return min;
    }
}

内层循环 j 在递减时，如果 x 和当前 nums[j] 相与不再发生变化，说明 x 不足以让当前位置 nums[j] 变小，即 x 以及不能去掉 nums[j] 表示的集合中的比特位 1。而 nums[j-1]、nums[j-2] … nums[0] 都和 nums[j] 相与过，能被去掉的比特位 1 早就被 nums[j] 所表示的集合去掉了，因此 x 与 nums[j-1]、nums[j-2] … nums[0] 进行与运算也不会发生变化。

复杂度分析：

  • 时间复杂度：O(nlog⁡U)O(n\log U)，其中 n 是 arr 的长度，U=max⁡(arr)U=\max(arr)。由于 229−1<109<230−12^29 −1<10^9 <2^{30} −1，二进制数对应集合的大小不会超过 29，因此在 AND 运算下，每个数字至多可以减少 29 次。总体上看，二重循环的总循环次数等于每个数字可以减少的次数之和，即 O(nlog⁡U)O(n\log U)。
  • 空间复杂度：O(1)O(1)。

计数问题

AND 运算的计数问题

🟥 3209. 子数组按位与值为 K 的数目 - 力扣（LeetCode）

给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中有多少个 子数组 满足：子数组中所有元素按位 AND 的结果为 k 。

List + 原地去重法

在上一节的 OR/AND 运算中，求的是答案的最值。内层循环遇到 (nums[j] | x) == nums[j] 就可以提前终止了，从而达到降低内层时间复杂度的效果。而本题中要求统计子数组运算后与给定 k 相等的个数，如果 (nums[j] | x) == nums[j] 就跳出内层循环，当 k==nums[j]，答案 ans 就不能得到正确累计从而出现遗漏状况。

一个解决方法是另外维护一个 List，存储子数组运算结果以及该结果对应的数量。并且不时去重合并，从而达到降低时间复杂度的效果。

数组原地去重请复习此题：🟩 26. 删除有序数组中的重复项 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public long countSubarrays(int[] nums, int k) {
        long ans = 0;
        int len = nums.length;
        List<int[]> ls = new ArrayList<>();// 位与结果，子数组的数量
        for(int i=0;i<len;i++){
            int x = nums[i];
            
            ls.add(new int[]{x,1});
            for(int j=0;j<ls.size();j++){
                int[] e = ls.get(j);
                e[0]&=x;
                if(e[0]==k)ans+=e[1];
            }

            // 原地去重合并
            int l=0;
            for(int j=1;j<ls.size();j++){
                int[] e = ls.get(j);
                int[] last_e = ls.get(l);
                if(e[0]==last_e[0]){
                    last_e[1] += e[1];
                    continue;
                }
                ls.set(l+1,e);
                l++;
            }
            ls.subList(l+1,ls.size()).clear(); // 维持 O(log U)
        }
        return ans;
    }
}

内部循环中，ls 大小保持在 O(log⁡U)O(\log U)，U=max⁡(nums)U=\max(nums)。

复杂度分析：

  • 时间复杂度：O(nlog⁡U)O(n\log U)，其中 n 是 nums 的长度，U=max⁡(nums)U=\max(nums)。
  • 空间复杂度：O(1)O(1)。

这个方法改写自 @灵茶山艾府 的模板方法，为了方便理解，我把原地去重的逻辑抽离出来。你可以试图将同级的两个内部循环合在一起写，就得到灵神的模板。

二分查找方法

注意到，每次外层迭代后，集合 nums[j] 值是非递减的。这时我们可以考虑 站内文章二分查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public long countSubarrays(int[] nums, int k) {
	long ans = 0;
	for (int i = 0; i < nums.length; i++) {
		int x = nums[i];
		for (int j = i - 1; j >= 0 && (nums[j] & x) != nums[j]; j--) {
			nums[j] &= x;
		}
		ans += lowerBound(nums, i, k + 1) - lowerBound(nums, i, k);
	}
	return ans;
}

// 此二分查找方法交给读者实现
private int lowerBound(int[] nums, int right, int target);

复杂度分析：

  • 时间复杂度：O(nlog⁡U+nlog⁡n)O(n\log U+n\log n)，其中 n 是 nums 的长度，U=max⁡(nums)U=\max(nums)。由于二进制数对应集合的大小不会超过 29，因此在 AND 运算下，每个数字至多可以减小 29 次。总体上看（除去二分），二重循环的总循环次数等于每个数字可以减小的次数之和，即 O(nlog⁡U)O(n\log U)。
  • 空间复杂度：O(1)O(1)。

个数维护方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public long countSubarrays(int[] nums, int k) {
        long ans = 0;
        int cnt = 0;
        for (int i = 0; i < nums.length; i++) {
            int x = nums[i];
            cnt += x == k ? 1 : 0;
            for (int j = i - 1; j >= 0 && (nums[j] & x) != nums[j]; j--) {
                cnt -= nums[j] == k ? 1 : 0; // 去除上一轮统计时留下的标记
                nums[j] &= x;
                cnt += nums[j] == k ? 1 : 0;
            }
            ans += cnt;
        }
        return ans;
    }
}

代码中，cnt 表示当层 i 中符合要求的答案数量。

复杂度分析：

  • 时间复杂度：O(nlog⁡U)O(n\log U)，其中 n 是 nums 的长度，U=max⁡(nums)U=\max(nums)。
  • 空间复杂度：O(1)O(1)。

GCD 最大公约数的计数问题

🟨 Problem - 475D - CGCDSSQ - Codeforces

Given a sequence of integers a1, ..., ana_1, ..., a_n and q queries x1, ..., xqx_1, ..., x_q on it. For each query xix_i you have to count the number of pairs (l, r) such that 1 ≤ l ≤ r ≤ n1 ≤ l ≤ r ≤ n and gcd(al, al + 1, ..., ar) = xigcd(a_l, a_{l + 1}, ..., a_r) = x_i.

gcd(v1, v2, ..., vn)gcd(v_1, v_2, ..., v_n) is a greatest common divisor of v1, v2, ..., vnv_1, v_2, ..., v_n, that is equal to a largest positive integer that divides all viv_i.

Input
The first line of the input contains integer n,(1 ≤ n ≤ 105)n, (1 ≤ n ≤ 10^5), denoting the length of the sequence. The next line contains n space separated integers a1, ..., an,(1 ≤ ai ≤ 109)a_1, ..., a_n, (1 ≤ a_i ≤ 10^9).

The third line of the input contains integer q,(1 ≤ q ≤ 3 × 105)q, (1 ≤ q ≤ 3 × 10^5), denoting the number of queries. Then follows q lines, each contain an integer xi,(1 ≤ xi ≤ 109)x_i, (1 ≤ x_i ≤ 10^9).

Output
For each query print the result in a separate line.

image.png

此题中，GCD 的运算性质和与运算类似。

此题与前面题目不同的是，它会有 q 组询问；而前面题目只有 1 组询问，这时就需要 Map 来存储不同询问的答案。

以下是输入输出代码结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.util.Scanner;
import java.util.Arrays;
import java.util.Map;
import java.util.HashMap;
 
public class Main{
    
    public static void main(String[] args) {
    	Scanner in = new Scanner(System.in);
    	// 注意 hasNext 和 hasNextLine 的区别
    	int T = in.nextInt();
    	int[] nums = new int[T];
    	
    	for(int i=0;i<T;i++){
    	    int e = in.nextInt();
    	    nums[i] = e;
    	}
    	Map<Integer,Long> map = new HashMap<>();
    	solution(nums,map);
    	int Q = in.nextInt();
    	while (Q--!=0) { // 注意 while 处理多个 case
    		int q = in.nextInt();
    		System.out.println(map.getOrDefault(q,0L));
    	}
    }
    
    public static void solution(int[] nums,Map<Integer,Long> map){
        // ...
    }
    
    public static int gcd(int a,int b){ // 原理是辗转相除法（迭代版本）
        while(b!=0){
            a%=b;
            a^=b;
            b^=a;
            a^=b;
        }
        return a;
    }
}

我们所需要做的是填充 solution 这个核心代码。

个数维护方法

此题是上面提到的🟥 3209. 子数组按位与值为 K 的数目 - 力扣（LeetCode） 个数维护方法 Map 版。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void solution(int[] nums,Map<Integer,Long> map){
	int len = nums.length;
	Map<Integer,Long> cntMap = new HashMap<>();
	for(int i=0;i<len;i++){
		
		int x = nums[i];
		// cnt+= x==k? 1:0;
		cntMap.put(x,cntMap.getOrDefault(x,0L)+1L);
		for(int j=i-1;j>=0&&gcd(nums[j],x)!=nums[j];j--){
			
			cntMap.put(nums[j],cntMap.getOrDefault(nums[j],0L)-1L);
			if(cntMap.get(nums[j])==0)cntMap.remove(nums[j]); // 这是必要的，它能降低时间复杂度 维持 O(log U)
			nums[j] = gcd(nums[j],x);
			cntMap.put(nums[j],cntMap.getOrDefault(nums[j],0L)+1L);

		}
		for(int k:cntMap.keySet()){
			map.put(k,map.getOrDefault(k,0L)+cntMap.get(k));
		}
	}
}

List + 原地去重法

这里只给出 solution 方法的实现，将此函数替换上一节代码中相应函数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public static void solution(int[] nums,Map<Integer,Long> map){
	int len = nums.length;
	List<int[]> ls = new ArrayList<>(); // gcd cnt
	for(int i=0;i<len;i++){
		
		int x = nums[i];
		// cnt+= x==k? 1:0;
		map.put(x,map.getOrDefault(x,0L)+1L);
		ls.add(new int[]{x,1});

		for(int j=0;j<ls.size()-1;j++){
			int[] e = ls.get(j);
			int newgcd = gcd(e[0],x);
			map.put(newgcd,map.getOrDefault(newgcd,0L)+Long.valueOf(e[1]));
			e[0] = newgcd;
		}
		// 原地去重
		int k=0;
		for(int j=1;j<ls.size();j++){
			if(ls.get(j)[0]==ls.get(k)[0]){
				// int[] e = ls.get(k);
				ls.get(k)[1]+= ls.get(j)[1];
				continue;
			}
			ls.set(k+1,ls.get(j));
			k++;
		}
		ls.subList(k+1,ls.size()).clear();
	}
}

相关题目：

后续计划

  • 补充 CF1632D、蓝桥杯真题相关题解

本文参考