| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
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