Attempting to Extend Segment Trees to Arbitrary Subsets

Revision en2, by Noam527, 2022-06-03 22:48:32

Throughout the last several weeks I have tried to invent, and tackle, a generalization of segment trees (although now it doesn't fit to name it "segment trees"... see for yourself). The results are very few and special-purposed (and not so good, if you ask me), but the problem was very appealing and fun to think about.

The purpose of this blogpost is to share my experience with this problem, in order to strike curiousity in at least a few people, and also to let bright-minded users tackle this problem together, and possibly achieve better results.

So, there is no tl;dr. Sorry :)

The Motivation and The Problem

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en17 English Noam527 2022-06-12 23:51:32 0 (published)
en16 English Noam527 2022-06-12 23:50:46 3484 Tiny change: 'nteresting right now, but I do' -> 'nteresting, but I do'
en15 English Noam527 2022-06-12 22:50:21 4507 Tiny change: 'pressing $O \left( \f' -> 'pressing $\Omega \left( \f'
en14 English Noam527 2022-06-09 22:25:20 124
en13 English Noam527 2022-06-05 14:09:50 216 Tiny change: ' you want.' -> ' you want.\n\n'
en12 English Noam527 2022-06-05 13:41:06 3258
en11 English Noam527 2022-06-05 13:08:49 1115
en10 English Noam527 2022-06-05 11:59:13 168 Tiny change: ' is:\n\n$$\left\lcei' -> ' is:\n\n$$d(G) \coloneqq \left\lcei'
en9 English Noam527 2022-06-05 01:15:15 25 Tiny change: 'er upto a constant factor of' -> 'er upto a factor of'
en8 English Noam527 2022-06-05 01:12:15 197 Tiny change: 'ices $S = {v_1, \ldots, v_m}$ then it' -> 'ices $S = \{v_1, \ldots, v_m\}$ then it'
en7 English Noam527 2022-06-05 01:00:35 2316
en6 English Noam527 2022-06-04 02:55:54 2592 Tiny change: 'n$$\lceil \rceil$$\' -> 'n$$\lceil \max_{\empty \neq S \subseteq V} \rceil$$\'
en5 English Noam527 2022-06-04 01:20:52 909 Tiny change: 'cs (well, I don't c' -> 'cs (well, at least I don't c'
en4 English Noam527 2022-06-04 00:49:42 4705 Tiny change: 'very good.\n</spoil' -> 'very good. Generally this can get up to $O(V)$.\n</spoil'
en3 English Noam527 2022-06-03 23:28:23 2738 Tiny change: ' $\forall i \in [m]$' -> ' $\forall 0 \leq i < m, S_i \subseq [n]$'
en2 English Noam527 2022-06-03 22:48:32 4
en1 English Noam527 2022-06-03 22:48:19 700 Initial revision (saved to drafts)