A Sierpinski Triangle Data Structure for Efficient Array Value Update and Prefix Sum Calculation
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929266967445504 |
|---|---|
| author | Harrison, Brent Necaise, Jason Projansky, Andrew Whitfield, James D. |
| author_facet | Harrison, Brent Necaise, Jason Projansky, Andrew Whitfield, James D. |
| contents | The binary indexed tree, or Fenwick tree, is a data structure that can efficiently update values and calculate prefix sums in an array. It allows both of these operations to be performed in $O(\log_2 N)$ time. Here we present a novel data structure resembling the Sierpinski triangle, which accomplishes these operations with the same memory usage in $O(\log_3 N)$ time instead. We show this order to be optimal by making use of a connection to quantum computing. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_03990 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Sierpinski Triangle Data Structure for Efficient Array Value Update and Prefix Sum Calculation Harrison, Brent Necaise, Jason Projansky, Andrew Whitfield, James D. Data Structures and Algorithms The binary indexed tree, or Fenwick tree, is a data structure that can efficiently update values and calculate prefix sums in an array. It allows both of these operations to be performed in $O(\log_2 N)$ time. Here we present a novel data structure resembling the Sierpinski triangle, which accomplishes these operations with the same memory usage in $O(\log_3 N)$ time instead. We show this order to be optimal by making use of a connection to quantum computing. |
| title | A Sierpinski Triangle Data Structure for Efficient Array Value Update and Prefix Sum Calculation |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2403.03990 |