| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3447 |
| 6 | Um_nik | 3387 |
| 7 | heuristica | 3322 |
| 8 | turmax | 3317 |
| 9 | tourist | 3307 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 156 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 143 |
| 5 | Errichto | 139 |
| 6 | adamant | 137 |
| 7 | AmShZ | 135 |
| 8 | maroonrk | 133 |
| 9 | BledDest | 132 |
| 10 | qwexd | 129 |
I am interested in knowing if there is a data structure that can offer better than O(log n) average complexity and offers the following 2 operations:
Increment x-> V[x] = 1 (all elements are initially 0) Query (1->y) all query are 1 based...
I know I will have O(n) increases and O(n) queries and want better than O(n log n) total time...
What is the "query" operation doing — summing, checking if anything in the range is a set bit, or something else entirely?
Summing. For checking if anything in the range has a set bit, one could use rmq and obtain a theoretical O(n) for preprocessing and O(1) query.
You would need RMQ with updates for that. Can it be implemented in linear time?
probably not, I have a few things different though... 1) I know my values are 0 and 1 only 2) I know i have at most n queries and n modifications and I want a total of under O(n log n) so it can be amortized O(n) or even O(n log logn ) 3) All my queries are 1->y which usually does not help... 4) I know the operations from the beginning