Attempting to Extend Segment Trees to Arbitrary Subsets

Правка en2, от 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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en17 Английский Noam527 2022-06-12 23:51:32 0 (published)
en16 Английский Noam527 2022-06-12 23:50:46 3484 Tiny change: 'nteresting right now, but I do' -> 'nteresting, but I do'
en15 Английский Noam527 2022-06-12 22:50:21 4507 Tiny change: 'pressing $O \left( \f' -> 'pressing $\Omega \left( \f'
en14 Английский Noam527 2022-06-09 22:25:20 124
en13 Английский Noam527 2022-06-05 14:09:50 216 Tiny change: ' you want.' -> ' you want.\n\n'
en12 Английский Noam527 2022-06-05 13:41:06 3258
en11 Английский Noam527 2022-06-05 13:08:49 1115
en10 Английский Noam527 2022-06-05 11:59:13 168 Tiny change: ' is:\n\n$$\left\lcei' -> ' is:\n\n$$d(G) \coloneqq \left\lcei'
en9 Английский Noam527 2022-06-05 01:15:15 25 Tiny change: 'er upto a constant factor of' -> 'er upto a factor of'
en8 Английский 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 Английский Noam527 2022-06-05 01:00:35 2316
en6 Английский Noam527 2022-06-04 02:55:54 2592 Tiny change: 'n$$\lceil \rceil$$\' -> 'n$$\lceil \max_{\empty \neq S \subseteq V} \rceil$$\'
en5 Английский 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 Английский 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 Английский Noam527 2022-06-03 23:28:23 2738 Tiny change: ' $\forall i \in [m]$' -> ' $\forall 0 \leq i < m, S_i \subseq [n]$'
en2 Английский Noam527 2022-06-03 22:48:32 4
en1 Английский Noam527 2022-06-03 22:48:19 700 Initial revision (saved to drafts)