Algorithm - Maximum subarrays with sum and OR

Question

I was thinking on the following problem:
Given an array A. The value of an interval from i to the index j is defined as follows:

Take the maximum value from that interval, and add it to the OR value of all the numbers from this interval(which equals a[i] OR a[i+1] OR ... OR a[j]).

Now lets suppose, our arrays length is N. Now we need to determine the value of the interval with the highest value, which has a length k where k = 1,2,3...N(so we need to answer for every possible k, and therefore we need approximately O(log N) or O(log^2 N) time to answer for a given k value). The dataset is large enough(N<=100000), so I can't use an algorithm with complexity O(N^2), with which I was able to come up.

My only idea was an N x log N big two dimension array, where I can store datas, with which I can determine OR in O(log N) time, but I'm out of ideas. Please, help me.

Thank you in advance!

Answer 1

Denote an interval with $(i, j)$, meaning it is the interval from $a[i]$ to $a[j]$. Denote by $OR(i, j)$ the value $a[i]$ or $a[i+1] \ldots a[j]$. For each $k$, we want to find $i$ that maximizes (or minimize) $OR(i, i+k-1)$.

For each $i$, consider the set $\{OR(i, j) | j \le i\}$ (that is, all the possible different values of intervals starting at position $i$). Let the maximum value of any of the elements be $M$. Then, the set will contain at most $O(\log M)$ distinct values (to see this, suppose $OR(i, j) \not = OR(i, j+1)$. Then, one of the bits from $OR(i, j)$ that was zero must be one in $OR(i, j+1)$. But there are at most $\log M$ bits, so this can only happen $O(\log M)$ times.

Thus, for each $i$, calculate all the possible distinct values of $OR(i, j)$ (can be done quickly in $O(\log n)$ for each $i$). Computing the maximum/minimum for each $k$ is now trivial.

EDIT: Expanded Answer. Here's the algorithm

1) For each $0 \le i \le \log M$, create a data structure $D_i$ from which you can compute the following: given an index $j$, find the first index $f \le j$ such that the $i$-th bit of the number at index $f$ is 1.

2) For each $0 \le i \le N$ and for all possible indices $j$, query $D_j$ at position $i$ to find the first index $f_j$ whose $j$-th bit is 1 (using $D_j$). Note that $f_j$ may be equal $i$ for some $j$.

3) Sort all the $f_j$ values, and make them unique. For every prefix of this sequence, compute their OR = $p$. Let $a_k$ be our potential answer for a given $k$. Suppose $f_z$ is the largest of index of all the $f_j$ values that makes up $p$. Add $p$ to the potential answers for $a_{f_j - f_0}$.

4) For each $k$, the maximum value is either one of the values of $a_k$, or is equal to the maximum value for less $k$.

This is $O(N \log^2 N)$. If you rather have pseudocode

for i in range(N):
  zs = set()
  for j in range(log M):
    zs.add(first index k >= i whose j-th bit is one).
  orvalue = 0
  for v in sorted(zs):
    orvalue |= number[v]
    maybe_answer[v - i].push(orvalue)

best = 0
for k in range(N+1):
  best = max(best, max(maybe_answer[k]))
  print 'answer for k=' + k + ' is ' + best