Итак, многие из Вас знают как можно легко и просто хешировать множества, например, множество $$$s = { s_1, s_2, ..., s_n }$$$ можно захешировать числом $$$x^{s_1} + x^{s_2} + ... + x^{s_n}$$$ или даже $$$x_{s_1} \text{xor} ... \text{xor} x_{s_n}$$$ (где $$$x$$$ -- какое-то случайное число). С такими хешом можно поддерживать операции добавления и удаления элемента, слияния множеств, нахождения симметричной разности множеств и так далее. Но у такого подхода есть и достаточно серьезный минус, например, имея на руках только хеш мы никак не определим, содержится ли элемент в нашем множестве, какие вообще элементы содержатся в этом множестве ну и так далее. После недолгих рассуждений придумал простую (на этом надо сделать акцент) структуру данных, основанную на дереве отрезков, которая позволяет совершать различные операции с множествами и сравнивать эти самые множества за O(1).