Memproses ulang array untuk menghitung elemen dalam slice (reduksi menjadi RMQ?)

Mengingat array bilangan , di mana adalah konstanta, saya ingin jawaban dalam query dalam bentuk: "berapa kali muncul dalam array antara indeks dan "? $a_1,\ldots,a_n$ $\leq k$ $k$ $O(1)$ $m$ $i$ $j$

Array harus preprocessed dalam waktu linier. Khususnya saya ingin tahu apakah ada pengurangan ke Range Minimum Query.

Ini sama dengan RMQ dalam kasus di mana dan Anda ingin menanyakan jumlah yang dalam interval. Jadi kita bisa menggunakan itu . ^{Saya tidak bisa menjawab pertanyaan saya sendiri karena keterbatasan SE.} $k=1$

algorithms arrays algorithm-design andy
sumber

Anda dapat mengurangi perbedaan elemen pada masalah Anda (dalam waktu linier). Mungkin berbicara tentang model sudah beres?

Aryabhata

@Aryabhata apa sebenarnya masalah perbedaan elemen? Sekarang saya membaca ini: en.wikipedia.org/wiki/Range_Queries

andy

Ini jauh lebih mudah daripada RMQ. Petunjuk: Karena k adalah konstanta, preprocessing dapat menghabiskan waktu secara proporsional dengan kn dan masih dihitung sebagai waktu linier.

Tsuyoshi Ito

@Aryabhata: Pengurangan yang saya pikir Anda bicarakan tidak bekerja karena k adalah konstanta dalam masalah ini.

Tsuyoshi Ito

Untuk jaga-jaga, jika array diberikan di awal dan tidak diperbarui sesudahnya, RMQ adalah berlebihan, seperti yang saya sarankan dalam komentar saya sebelumnya.

Tsuyoshi Ito

Jawaban:

$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$

Preprocessing

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]] ++

Pertanyaan

(menganggap saya, keduanya adalah batas inklusif)

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

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

Permintaan maaf untuk masalah apa pun dengan jawaban ini, ini adalah yang pertama.

Goldy
sumber