Poll: what do you call this well-known extension of segment tree?

Revision en4, by -is-this-fft-, 2022-09-07 07:26:00

For some reason, everyone refers to it with a different name which creates a lot of confusion. This debate comes up any time someone mentions any of the names, so let's have a poll to settle this thing once and for all.

Consider the following problem.

Problem. There is an array $$$A$$$ of length $$$10^{18}$$$, initially filled with zeros. You are given $$$q$$$ queries of the following form:

  • Given $$$l$$$ and $$$r$$$, find $$$A[l] + A[l + 1] + \cdots + A[r]$$$.
  • Given $$$i$$$ and $$$x$$$, set $$$A[i] \gets x$$$.

What do you call the data structure that solves the problem above in time $$$O(q \log C)$$$?

Details if you're not sure what I mean
  • Compressed segment tree
  • Dynamic segment tree
  • Implicit segment tree
  • Sparse segment tree
  • Lazy creation segment tree
  • I don't know this data structure
  • I'm green or below

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English -is-this-fft- 2022-09-07 07:26:00 4 Tiny change: ']$ and $[m, r]$, whe' -> ']$ and $[m + 1, r]$, whe'
en3 English -is-this-fft- 2022-01-15 21:35:33 48 Tiny change: 's:1,option' -> 's:1,option7] Lazy creation segment tree\n- [likes:1,option'
en2 English -is-this-fft- 2022-01-15 21:24:53 24
en1 English -is-this-fft- 2022-01-15 21:24:09 1304 Initial revision (published)