Как выяснилось, веревка нынче не входит в курс алгоритмов и структур данных для школьников, а высшее образование, как известно, для слабаков

ссылка на википедию для тех, кто считает, что я непонятно объясняю

Классичесая веревка

состоит из

  1. Типа
  2. Моноида над типом
  3. Бинарного дерева (без красок)
  4. ????????????
  5. foldl за O(1)`

И бонусом склейка и разрезание (и, как следствие, вставка и удаление) за O(log N). С сохранением сортировки

Реализовывать в коде мы её, конечно, не будем, потому что есть википедия

Заметим,

что прямое произведение пар (тип, моноид) является парой (тип, моноид)

Определим его следующим образом:

((A, ma) × (B, mb) = ((A, B), λ(a1, b1).λ(a2, b2).(ma a1 a2, mb b1 b2))

Таким образом, мы можем использовать веревку для того, чтобы вычислять свертку с произвольным числом моноидов за O(1).

Также

Мы можем использовать вместо естественной сортировки любой удобный нам порядок, чтобы быстро (O(log N) в худшем случае) вычислять свертку над произвольным отрезком.

Или даже

Собрать веревку из веревок, чтобы иметь возможность делать выборки по отдельным функциям. Например, возьмем массив данных с счетчика посещаемости, и сделаем группировку по пользователю. Каждой группе выделим свою веревку, а их корни соберем в суперверевку, в которой будет агрегация по всем пользователям. К сожалению, сортировку при выборке по всем пользователям мы уже не сможем использовать (разве что отсортировать по их id)

Напрашивается вывод

Засунуть веревку в базу данных. Было бы охуенно.

Вообще говоря, такого рода агрегация - типовая задача. Мы очень часто собираем руками огромные таблицы с группировкой по некоторым параметрам, чтобы гонять агрегации для статистики уже над полуагрегированным данными. Можно делать это тригерами в БД, можно руками делать транзакции из приложения, а круто было бы просто объявить веревку в базе данных и пусть она сама все считает.

И, на последок, народная мудрость. В военное время O(log N) = O(1)