Блог пользователя chill21

Distinct digits in a range using BIT
Автор chill21, история, 8 лет назад, По-английски

You are given an array of size n find number of distinct digits in the numbers in a given range ? I know how to do it with segment tree , please help me to do it with Binary indexed tree .

thanks in advance :)

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

You can use one BIT per digit so you can easily found the frequency of any given digit in a range. You can solve every query in O(D * log(N)) where D = 10.

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

You know how to do it with segment tree then you must be familiar with the logic. Then I guess problem is in the implementation part.
Here is my solution.

→ Ответить
»
8 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

By the way if you have multiple queries which can be processed offline, this can also be done using square root decomposition (also referred to as Mo's algorithm).

→ Ответить