Декартовы деревья по неявному ключу + сжатие пространства

Прежде чем читать эту статью, нужно понимать, что такое декартово дерево по неявному ключу (это тема не одной статьи, поэтому об этом лучше почитать тут). Сжатие пространста — метод, используемый для сжатия на отрезке данных. Например, вместо того, чтобы хранить множество {1, 1, 1, 2, 2, 2, 3, 1, 1} будем хранить {1 x 3, 2 x 3, 3 x 1, 1 x 2}.
Теперь попробуем сжимать пространство с помощью такого метода и иметь возможность выполнять онлайн операции с любым отрезком.

Сразу приведу свою реализацию таких деревьев

struct trep_node
{
   int x, y;
   trep_node *l, *r, *p;
   int width;
   int val;

   // Проталкивание ленивых операций
   void push()
   {
      // Место для вставки кода отложенных операций
   }

   // Сыновья изменились, нужно обновить текущую вершину
   void update()
   {
      x = width;
      if (l)
            x += l -> x;
      if (r)
            x += r -> x;
      if (l)
            l -> p = this;
      if (r)
            r -> p = this;
      // Вставить код обновления, в зависимости от того, что делает наша структура данных

   }

    trep_node(int _width, int _val)
    {
          // начальная инициализация
          // val - хранимое значение, width - ширина хранимого отрезка
         y = (rand() << 16) + rand();
         l = r = p = NULL;

         width = _width;
         val = _val;

         update();
	}
};

// объединить 2 дерева
trep_node* merge(trep_node *l, trep_node *r)
{
        if (l == NULL)
               return r;
        if (r == NULL)
               return l;
        if (l -> y >= r -> y)
        {
                l -> push();
                l -> r = merge(l -> r, r);
                l -> update();
                return l;
        }
        else
	{
                r -> push();
                r -> l = merge(l, r -> l);
                r -> update();
                return r;
         }
}

// Разрезать 1 дерево на 2
void split(trep_node *t, int x, trep_node *&l, trep_node *&r)
{
        if (t == NULL)
        {
              l = r = NULL;
              return;
        }
        t -> push();
        if ((t -> l == NULL ? 0 : t -> l -> x) >= x)
        {
                split(t -> l, x, l, t -> l);
                if (l != NULL)
                         l -> p = NULL;
                t -> update();
                r = t;
                return;
        }
        else if ((t -> l == NULL ? 0 : t -> l -> x) + t -> width <= x)
        {
                split(t -> r, x - (t -> l == NULL ? 0 : t -> l -> x) - t -> width, t -> r, r);
                if (r != NULL)
                      r -> p = NULL;
                t -> update();
                l = t;
                return;
        }
        else
        {
                // Самая интересная часть. Если граница раздела приходится на сам элемент, то нужно распилить сам элемент
                trep_node *t1 = new trep_node(x - (t -> l == NULL ? 0 : t -> l -> x), t -> val);
                trep_node *t2 = new trep_node(t -> width - t1 -> width, t -> val);
                l = merge(t -> l, t1);
                r = merge(t2, t -> r);
                l -> p = NULL;
                r -> p = NULL;
                delete(t);
         }
}

Заметим, что по сравнению с обычными декартовыми деревьями, у нас в структуре появилось свойство width — ширина отрезка, хранимого в нашей текущей вершине. А val — само значение.
Еще одно кардинальное изменение — функция split

else
	{
                // Самая интересная часть. Если граница раздела приходится на сам элемент, то нужно распилить сам элемент
		trep_node *t1 = new trep_node(x - (t -> l == NULL ? 0 : t -> l -> x), t -> val);
		trep_node *t2 = new trep_node(t -> width - t1 -> width, t -> val);
		l = merge(t -> l, t1);
		r = merge(t2, t -> r);
		l -> p = NULL;
		r -> p = NULL;
		delete(t);
	}

Здесь появился еще одна часть if. Которая относится к разделению отрезка на 2 подотрезка. И потом склейка в левую и правую часть.

Функцию merge менять не будем, т. к. в задаче, для которой я это использую на асимптотику это не влияет. Этим я решаю задачу сжатия пространства, и могу отвечать на запросы в онлайн. В принципе, если кому надо, можно переписать и функцию mergeб для объединения двух отрезков. Вместо того, чтобы считывать все возможные данные, задавать фиксированные отрезки, а потом бинпоиском искать нужные номера отрезков, и в дереве отрезков делать нужные изменения, я, за туже асимптотику обхожусь небольшим if. Правда приходится использовать декартовы деревья. Для меня так писать гораздо удобнее и быстрее. Может это кому — нибудь пригодится.

Автор: ryad0m

Источник