Distinct OR scores of increasing subsequences

Problem The score of a subsequence is the bitwise OR of all its elements (the empty subsequence has score 0). Given an integer array arr, find every distinct score value achievable by a strictly increasing subsequence of arr, and return the values sorted in ascending order.

Input / Output

• Input: int arr[n] — an array of integers.
• Output: int[] — all possible distinct score values, sorted ascending.

Constraints

• 1 <= n <= 10^4
• 1 <= arr[i] <= 1024 (so every score fits below 2048)
• Subsequences must be strictly increasing in value while preserving index order.

Example

• arr = [3, 2, 4, 6] → [0, 2, 3, 4, 6, 7]. Singletons give 2, 3, 4, 6; [2,4] gives 2|4 = 6 and [3,4] gives 3|4 = 7. Longer chains like [2,4,6] (OR 6) and [3,4,6] (OR 7) add no new values, and 0 comes from the empty subsequence. Note [4, 2, 4, 1] → [0, 1, 2, 4, 6]: the second 4 can extend the earlier 2 (indices in order, values increasing), but the trailing 1 extends nothing.

Expected approach

• Left-to-right DP keyed by ending value: let E[v] = the set of OR-masks of strictly increasing chains ending with value v. For each element x, the reachable set is {0} ∪ (union of E[v] for all v < x); the new chains ending at x are { m | x : m in reachable }. Merge those into E[x] and into a global answer set.
• Represent mask-sets as bitsets over [0, 2048) and keep a Fenwick (BIT) tree over values so the "union of E[v] for v < x" prefix query costs O(log maxV) bitset ORs; updates at x likewise touch O(log maxV) nodes.
• Processing elements in index order enforces the subsequence constraint automatically; querying at x−1 (strictly less) enforces strict increase, including duplicate values.
• Complexity: O(n · log(maxV) · 2048/64) word operations ≈ a few tens of millions for n = 10^4 — comfortably fast. Space O(maxV · 2048) bits.