Предварительная обработка массива для подсчета элемента в срезе (сокращение до RMQ?)

Для массива натуральных чисел , где - константа, я хочу ответить на запросов вида: «сколько раз появляется в массиве между индексами и "? $a_1,\ldots,a_n$ $\leq k$ $k$ $O(1)$ $m$ $i$ $j$

Массив должен быть предварительно обработан за линейное время. В частности, я хотел бы знать, есть ли сокращение до минимального диапазона запросов.

Это эквивалентно RMQ в случае, когда и вы хотите запросить количество единиц в интервале. Таким образом, мы можем использовать это . ^{Я не мог ответить на свой вопрос из-за ограничений SE.} $k=1$

algorithms arrays algorithm-design Энди
источник

Вы можете уменьшить четкость элементов в вашей проблеме (в линейное время). Возможно, говорить о модели в порядке?

Арьябхата

@Aryabhata, что именно проблема четкости элементов? Сейчас я читаю это: en.wikipedia.org/wiki/Range_Queries

andy

Это намного проще, чем RMQ. Подсказка: поскольку k является константой, предварительная обработка может проводить время, пропорциональное kn, и все равно считается как линейное время.

Цуёси Ито

@Aryabhata: сокращение, о котором я думаю, вы говорите, не работает, потому что k является константой в этой проблеме.

Цуёси Ито

На всякий случай, если массив дается в начале и не обновляется впоследствии, RMQ является излишним, как я предположил в моем предыдущем комментарии.

Цуёси Ито

Ответы:

$k$ $0..m$ $0\leq m \lt n$ $0..n$ $O(nk) = O(n)$ count[pos][elem] = occurences of 'elem' in the indices 0..pos $O(nk)$ $i,j$

предварительная обработка

initialise count[pos][elem] to 0 for all elem, pos
for pos=0 to n
  for num=0 to k
      count[pos][num] = (0 if pos==0 else count[pos-1][num])
  count[pos][arr[pos]] ++

запрос

(предполагается, что i, j являются включающими границами)

if i == 0
  return count[j][m]
else
  return count[j][m] - count[i-1][m]

$k$ count $O(\log n)$ $O(\log n)$

Извиняюсь за любые вопросы с этим ответом, это мой первый.

Goldy
источник