LogTrick算法

#算法

LogTrick 用于高效遍历所有子数组并计算连续运算结果（如与、或、最值等）。其核心逻辑是通过双重循环，利用运算的单调性进行剪枝优化：

  • 遍历策略：外层循环枚举右端点i，内层循环从i-1向左遍历，逐步将当前元素arr[i]与前面元素进行运算（如arr[j] &= arr[i]）。
  • 优化条件：当发现运算结果不再变化时（如arr[j] & arr[i] == arr[j]），立即终止内层循环，避免无效计算。
  • 时间复杂度：通过剪枝优化，时间复杂度可从暴力枚举的O(n²)降至O(nlogC)（C为元素值域范围）。 LogTrick 能快速收敛到稳定值，减少重复计算。

力扣相关题目

LogTrick做法(简洁高效)

//LogTrick算法
vector<int> smallestSubarrays(vector<int>& nums){
    int n = nums.size();
    vector<int> ret(n);
    for (int i = 0;i < n;i++){
        ret[i] = 1;
        int x = nums[i];
        //不再变化时停止第二层循环
        for (int j = i - 1;j >= 0 && (nums[j] | x) != nums[j];j--){
            nums[j] |= x;//利用后面更新前面，快速收敛
            ret[j] = i - j + 1;//更新答案
        }
    }
    return ret;
}

普通算法后缀+二分做法(比较容易想)

vector<int> smallestSubarrays(vector<int>& nums) {
    int n = nums.size();
    vector<int>ans(n);
    vector<vector<int>>sum(n + 1, vector<int>(32));
    int t = 0;//这一位开始最大或值应该是多少
    vector<int>v(32);
    for (int i = n - 1;i >= 0;i--) {
        sum[i] = sum[i + 1];
        t |= nums[i];
        for (int j = 0;j < 32;j++) {
            if ((nums[i] >> j) & 1) {
                sum[i][j]++;
            }
            if ((t >> j) & 1)v[j] = 1;
        }
        //二分
        int l = i, r = n + 1;
        while (l + 1 != r) {
            int mid = (l + r) / 2;
            int flag = 1;
            for (int j = 0;j < 32;j++) {
                if (v[j] && !(sum[i][j] - sum[mid][j])) {
                    flag = 0;break;
                }
            }
            if (flag)r = mid;
            else l = mid;
        }
        ans[i] = r - i;
    }
    return ans;
}

联系方式 - 如果你 喜欢 我的话~

GitHubbilibiliCSDN

ZHM