子数组按位或操作 图解题解

按位或的不同结果，到底在数什么

给整数数组 arr，把每个非空子数组（连续一段，不能跳着取）各做一遍按位或，问有多少个不同的值。按位或就是把一段的数逐位比较，某位只要有一个是 1，结果那位就是 1。题面 arr=[1,2,4] 能或出 1、2、3、4、6、7 六个值，答案 6；arr=[0,0] 三段全为 0 只有一种，答案 1。数的是不同结果个数，不是子数组条数。

为什么把每个子数组都或一遍会超时

长度 n 的数组有 n(n+1)/2 个子数组，逼近 O(n²) 个（大 O 记号描述规模变大时运算量怎么涨）。把每段从头或到尾又各要 O(n) 次，硬枚举奔着 O(n³) 去，n 到十万扛不住。更亏的是以同一右端点结尾的段大量重叠、前半截反复重或，这些或值该攒着复用。

盯住『以当前元素结尾』的那一小撮或值

只盯以当前这个数结尾的所有子数组各自的按位或值，收进集合 cur（自动去重）。关键是 cur 永远很小：按位或有个死性子——只把二进制位从 0 变成 1，从不把 1 清回 0。固定右端点、左端点往左扩，这段的或值只增不减。题目里的数不超过 10^9，只占 30 个二进制位；或值每真变大一次至少点亮一个新位，最多点亮 30 次就涨不动了。所以以任一位置结尾，不同或值至多约 30 个——cur 恒小的根就在这。

新一轮的或值集合，凭什么只用旧集合推

滚到下一个数 x，不必重扫前面。以 x 结尾的子数组只有两类：只有 x 自己的，或值就是 x；由前一段接上 x 而来的，或值等于那段旧或值再或上 x。上一轮的 cur 正好存着以上一个数结尾的全部或值，把每个都或一遍 x、再补上 x 自己，就是新 cur：new cur = {x | y ：y 属于旧 cur} 再并上 {x}。每得一轮就并进总集合 ans（同样去重），扫完 arr，ans 的大小即答案。这套滚着推正是动态规划：把以每个位置结尾的小答案攒下来直接复用。

拿 [1,2,4] 把集合一轮轮滚出来

拿题面 arr=[1,2,4] 滚一遍，ans 起初为空。数 1：cur={1}，ans={1}。数 2：旧 cur={1}，1 或 2 得 3，再补上 2，cur={2,3}，ans 新增 2、3 成 {1,2,3}。数 4：旧 cur={2,3}，2 或 4 得 6、3 或 4 得 7，再补 4，cur={4,6,7}，ans 新增 4、6、7 成 {1,2,3,4,6,7}。扫完 ans 里正好六个值，答案 6，和题面对上。

漏掉『只含自己』那个子数组，答案为什么会少一截

每轮忘了往 cur 补上 x 自己，是最常见的写反：单个元素单独成段的或值全丢，只有一个数的输入会连它本身都数不到。复杂度上，每个位置的 cur 至多约 30 个，扫 n 个数各做一次或，时间 O(n·30)、接近线性；ans 最多攒约 30n 个值，空间 O(n·30)，cur 只占 O(30)。两个边界想清：数组全是 0 时每段或值都是 0，答案只能是 1，别数成子数组条数；各数二进制位完全错开时或值组合最多，cur 塞得最满也不超 30 个。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def subarrayBitwiseORs(self, arr: List[int]) -> int:
        ans = set()
        s = set()
        for x in arr:
            s = {x | y for y in s} | {x}
            ans |= s
        return len(ans)

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int subarrayBitwiseORs(vector<int>& arr) {
        unordered_set<int> ans;
        unordered_set<int> s;
        for (int x : arr) {
            unordered_set<int> t;
            for (int y : s) {
                t.insert(x | y);
            }
            t.insert(x);
            ans.insert(t.begin(), t.end());
            s = move(t);
        }
        return ans.size();
    }
};

Java

import java.util.*;
class Solution {
    public int subarrayBitwiseORs(int[] arr) {
        Set<Integer> ans = new HashSet<>();
        Set<Integer> s = new HashSet<>();
        for (int x : arr) {
            Set<Integer> t = new HashSet<>();
            for (int y : s) {
                t.add(x | y);
            }
            t.add(x);
            ans.addAll(t);
            s = t;
        }
        return ans.size();
    }
}