\Section{Пополняемые структуры}{28 сентября}{Шевченко Илья}



\Subsection{Add $\rightarrow$ Merge}

Научимся делать $Merge$ структур, для которых определена операция $Add$. Для этого достаточно добавить все элементы меньшей по размеру структуру в большую.

\THE{Merge}
\begin{code}
	Merge(A,B){
		if A.size > B.size
			swap(A,B)
		foreach a in A
			B.insert(a)
		return B	
	}	
\end{code}

\begin{Thm}
	Если суммарное количество элементов в структурах не превосходит $n$, то любая последовательность вызовов $Merge$ выполнится за $\O(n\log n\cdot Add)$, где $Add$ - временная сложность операции добавления.
	\begin{proof}
		Каждый раз, когда для элемента вызывается функция $Add$ размер множества, в котором он содержится увеличивается хотя бы в два раза. Таким образом, для каждого элемента $Add$ не может быть вызван более $\log_2 n$ раз. Элементов $n$, следовательно всего вызовов не более $n\log_2 n$, ч.т.д.
	\end{proof}
\end{Thm}

\Subsection{Build, Get $\rightarrow$ Add}

\Subsubsection{С помощью корневой оптимизации}

Теперь научимся добавлять $Add$ в структуру, которая умеет делать $Build$ и $Get$ (функция $Get$ должна быть аддитивной). 

Для этого разобьём структуру на несколько, каждая из которых будет размера $m$. В функции $Add$ будем просто делать $Build$ от того, что есть в текущей структуре и нового элемента. Временная сложность - $\O(Build(m))$

\THE{Add}
\begin{code}
	Add(parts,cur,x){
		if parts[cur].size = m
			cur++
		Build(parts[cur], x)
	}
\end{code}



В $Get$ будем пробегать по всем структурам, вызывать $Get$ от них, а затем брать $Get$ от всех результатов. Временная сложность - $\O(\frac{n}{m}Get(m))$

\THE{Get}
\begin{code}
	Get(parts){
		for A in parts
			res = combine(Get(A), res)
		return res	
	}	
\end{code}

Рассмотрим этот подход на примере структуры $SortedArray$, для которой $Build=Sort$ и $Get=lower\_bound$. В этой структуре для $Add$ можно использовать не $Build$, а обычную вставку в отсортированный массив за $\O(m)$. Тогда сложнность операции $Get$ - $\O(\frac{n}{m}\log m)$, а $Add$ - $\O(m)$. Возьмём $m$ равное $\sqrt{n\log n}$. Тогда сложность обеих операций будет $\O(\sqrt{n\log n})$.

\Subsubsection{С помощью представления в двоичной системе счисления}

Пусть в структуре $n$ элементов. Рассмотрим разложение числа $n$ в двоичной системе счисления - $n=\sum 2^{k_i}$. Будем поддерживать несколько (не более $\log_2 n$) структур размера $2^{k_i}$, для каждого слогаемого из суммы. 

Теперь $Add(x)$ будет выглядеть следующим образом: создадим новую структуру размера 1 из $x$, пока у нас есть структуры одного размера вызываем от них $Build$, добавляем его к нашим структурам, а те две удаляем.	

\begin{Thm}
	Пусть $Add=\log N + k_i$, где $k_i$ - суммарное время работы вызовов $Build$ сделанных в этом вызове функции $Add$. Тогда для серии вызовов функции $Add$ - $\sum k_i \le Build(N\log N)$
	\begin{proof}
		Пусть в процессе исползования структуры были сделаны вызовы $Build(b_1), Build(b_2), ..., Build(b_m)$. Будем использовать лемму $\sum Build(b_i)\le Build(\sum b_i)$ без доказательства.
		Каждый элемент входил в один из вызовов $Build$ не более $\log_2 N$ раз, всего элементов $N$. Тогда по лемме - $\sum Build(b_i)\le Build(\sum b_i)\le Build(N\log N)$, ч.т.д.
	\end{proof}
\end{Thm}

\Subsection{Get $\rightarrow$ Delete}

Научимся удалять элемент из структуры, которая поддерживает $Get$ (функция $Get$ должна быть обратимой). Для этого просто заведём структурку $Deleted$ и при вызове $A.Get()$ будем возвращать $A.Get() - Deleted.Get()$.