Closest Position of Each Bit
My first idea was to count occurrences each bit, and use this information for a sliding window. \n\nThe implementation was tricky, so I decided to just use a se
My first idea was to count occurrences each bit, and use this information for a sliding window. \n\nThe implementation was tricky, so I decided to just use a segment tree for range bitwise OR queries (second solution below).\n\n> Even though the second solution is O(n log n), its runtime is a bit better. With `n` limited to `100,000`, `log2 n` is `~17`, So, it needs `17 * 100,000` operations, while the first solution takes `30 * 100,000` (30 bits to check for each number).\n\nLater, I realized that we do not need to count each bit if we process numbers right-to-left. We just need to track the closest position of each bit\n\n#### Closest Position of Each Bit\nWe go right-to-left, and use `closest` array to track the closest (or smallest) position of each bit.\n\nWe can then use the maximum position among all bits to find out the shortest subarrays with all bits set.\n\nHere is an example for `[4, 2, 1, 5, 3, 1, 2, 1]` case:\n![image](https://assets.leetcode.com/users/images/95a79fb0-3118-4d25-83f5-a187a2ff1a9c_1663774308.642698.png)\n\n**C++**\n```cpp\nvector<int> smallestSubarrays(vector<int>& nums) {\n    vector<int> res(nums.size()), closest(30);\n    for (int i = nums.size() - 1; i >= 0; --i) {\n        for (int b = 0; b < 30; ++b)\n            if (nums[i] & (1 << b))\n                closest[b] = i;\n        res[i] = max(1, *max_element(begin(closest), end(closest)) - i + 1);\n    }\n    return res;\n}   \n```\n#### Segment Tree\nWe can use a segment tree to query bitwise XOR of any interval in O(log n).\n\n**C++**\n```cpp\nint st[2 * (1 << 17)] = {}; // 2 ^ 16 < 100000 < 2 ^ 17\nclass Solution {\npublic:\nint bit_or(int l, int r, int tl, int tr, int p = 1) {\n    if (l > r) \n        return 0;\n    if (l == tl && r == tr)\n        return st[p];\n    int tm = (tl + tr) / 2;\n    return bit_or(l, min(r, tm), tl, tm, p * 2) | bit_or(max(l, tm + 1), r, tm + 1, tr, p * 2 + 1);\n}    \nint build(vector<int>& nums, int tl, int tr, int p = 1) {\n    if (tl == tr)\n        return st[p] = nums[tl];\n    int tm = (tl + tr) / 2;\n    return st[p] = build(nums, tl, tm, p * 2) | build(nums, tm + 1, tr, p * 2 + 1);\n}     \nvector<int> smallestSubarrays(vector<int>& nums) {\n    vector<int> res;\n    build(nums, 0, nums.size() - 1);\n    for (int i = 0, j = 0; i < nums.size(); j = max(++i, j)) {\n        while (bit_or(i, j, 0, nums.size() - 1) < bit_or(i, nums.size() - 1, 0, nums.size() - 1))\n            ++j;\n        res.push_back(j - i + 1);\n    } \n    return res;\n}\n};\n```
[]