%% texify: XeLaTeX + MakeIndex + BibTeX, modified:
%% texify
%% --pdf
%% --engine=xelatex
%% --tex-option=$synctexoption // You may delete this, affords to skip from preview to code in one click, that i seldom do
%% --tex-option=-8bit // Else minted fails on tabs
%% --tex-option=--shell-escape // For minted to be alive
%% $fullname
%% I prefer to typeset with TeXworks for better view of errors and warnings. It's hard to read all log file. 

\documentclass[12pt]{book}
\usepackage{polyglossia} %% Better than babel on XeLaTeX
\usepackage{amsmath, amssymb} %% Cool math!
\usepackage{color} %% Coloring almost anything
\usepackage[russian]{hyperref} %% Clickable links is pdf
%% WARNING: latest minted is used. Download from github!
%% Works fine, though
\usepackage{minted} %% Highlighting code. Installation is hard: requires python2 and script Pygments. Look at documentation for help!
\usepackage[math-style=ISO,vargreek-shape=unicode]{unicode-math} %% MAGIC! INCLUDE AS LAST!

\setdefaultlanguage[spelling=modern]{russian} %% Languages for polyglossia
\setotherlanguage{english}

\defaultfontfeatures{Ligatures={TeX}} %% Fonts and ligatures.
\setmainfont{CMU Serif} %% There are original Knuth's fonts in Unicode, called Computer Modern Unicode. Download anywhere, just install them
\setsansfont{CMU Sans Serif}
\setmonofont{CMU Typewriter Text}  
\setmathfont{Latin Modern Math} %% Download too. You may change it :)
%% Patch for Latin Modern Math
\newcommand{\Setminus}{\mathbin{\backslash}}

%% Magic as black as my working table
\DeclareSymbolFont{cyrletters}{\encodingdefault}{\familydefault}{m}{it}
\newcommand{\makecyrmathletter}[1]{%
  \begingroup\lccode`a=#1\lowercase{\endgroup
  \Umathcode`a}="0 \csname symcyrletters\endcsname\space #1
}
\count255="409
\loop\ifnum\count255<"44F
  \advance\count255 by 1
  \makecyrmathletter{\count255}
\repeat
%% Simpy adds cyrillic to maths!

\frenchspacing %% One space before sentence, not two!

%% Shortcuts:
\def\la{\leftarrow}
\def\ra{\rightarrow}
\def\lra{\leftrightarrow}
\def\La{\Leftarrow}
\def\Ra{\Rightarrow}
\def\Lra{\Leftrightarrow}
\def\lrh{\leftrightharpoons}
\def\btu{\bigtriangleup}

\def\N{\mathbb{N}}
\def\Z{\mathbb{Z}}
\def\Q{\mathbb{Q}}
\def\R{\mathbb{R}}
\def\C{\mathbb{C}}

\def\LraDef{\stackrel{\mathrm{Def}}{\Lra}}
\def\eqDef{\stackrel{\mathrm{Def}}{=}}

% ======================================

%% Change Chapter and Section numeration style
\renewcommand{\thechapter}{\Roman{chapter}}
\renewcommand{\thesection}{\thechapter.\arabic{section}}

%% Indent for first par in chapter
\makeatletter
\renewcommand{\chapter}{\clearpage %% no double page, only one
\thispagestyle{empty}%% not plain, empty. wanna number of page!
\global\@topnum=0
\@afterindenttrue %% Set to true!
\secdef\@chapter\@schapter}
\makeatother

%% Environment for theorem body
\newcounter{theorem}[section]
\renewcommand{\thetheorem}{\thesection.\arabic{theorem}}
\newcommand*{\theoremheader}[1]{\par\refstepcounter{theorem}%
\textbf{Теорема \thetheorem.} #1}
\newenvironment*{theorem}[1]{
	\theoremheader{#1}%
}{%
\par
}

%% Environment for consequence body
\newcounter{conseq}[theorem]
\renewcommand{\theconseq}{\arabic{conseq}}
\newcommand*{\conseqheader}{\par\refstepcounter{conseq}%
\textit{Следствие \thetheorem.} }
\newenvironment*{conseq}{
	\conseqheader%
}{%
\par
}

%% Environment for proof body. I like this style, but you are free to change it.
\newenvironment{proof}{%
\par$\blacktriangleright$%
}{%
\hfill$\blacktriangleleft$\par%
}

%% Environment for definitions. Pretty raw one.
\newenvironment{Def}{%
\par$\mathfrak{Def\colon}$%
}{%
\par
}

%% Environment for remarks.
\newenvironment{Rem}{%
\par\textit{REM: }%
}{%
\par
}

% ==================================

%% In-line code highlighting. Using: \py|a = input()|, where | is not in code!!!
\newmintinline[cinl]{c}{} %\c is defined, use \cinl or \cpp :(
\newmintinline[cpp]{cpp}{}
\newmintinline[python]{python}{}
\newmintinline[bash]{bash}{}
\newmintinline[make]{make}{}

%% Escaped code highlighting. Using: \begin{cppcode} ... \end{cppcode}
\setminted{%
	obeytabs,tabsize=4,%tabs work!
	linenos,%line numbers!
	texcomments,%tex in code comments!
}
\newminted{c}{}
\newminted{cpp}{}
\newminted{python}{}
\newminted{bash}{}
\newminted{make}{}

% ==================================

\begin{document}
\chapter{Лекция от 9 сентября}
\section{Структуры данных}
\begin{enumerate}
	\item Online.\\
		На поступающий запрос сразу даётся ответ. Говоря о времени работы, подразумеваем время,
		затрачиваемое на обработку одного запроса.
	\item Offline.\\
		Запросы поступают <<пачками>>, ответы даются сразу на все запросы. Оценивается время, затрачиваемое на
		обработку всех запросов.
\end{enumerate}
	Существует другая классификация:
\begin{enumerate}
	\item Статические (Static Data).\\
		Можем отвечать на запросы вида <<Присутствует ли элемент $x$ в множестве $A$?>>, но не можем изменять
		само множество $A$.
	\item Динамические (Dynamic Data).\\
		Можем отвечать на запросы <<Присутствует ли элемент $x$ в множестве $A$?>> и, в отличие от Static Data,
		можем добавлять и удалять элементы $A$.
\end{enumerate}
Также важным разделением является:
\begin{enumerate}
\item Амортизированное время~--- среднее за все запросы.
$$ O(n)\text{ за }n\text{ запросов }=O_{аморт}(1)\text{ на запрос}$$
\item Real Time~--- максимум из времён каждого запроса. Важнее для больших сервисов (социальные сети, сайты...).
\end{enumerate}

\section{Стек, очередь, дек}
\begin{Def}
Интерфейс~--- заданная функциональность, но не заданная реализация.
\end{Def}

Интерфейсы стека, очереди и дека мы знаем. Дек (Deque) является очередью (Queue) и стеком (Stack).

Реализуем дек на массиве. Дек~--- отрезок на этом массиве, а также указатели на начало и конец отрезка. Поддерживаются операции добавления и удаления элементов в начало 
и в конец дека. Дополнительно можно реализовать операцию доступа к $i$-ому элементу (это элемент $head + i$ в массиве). Время выполнения каждой из операций 
$O(1)$. (Стек с доступом к любому элементу за $O(1)$ называется вектор).

\begin{center}
\includegraphics[height = 120pt]{theory-02-01.jpg}
\end{center}

Реализация: у нас есть отрезок выделенной памяти и указатели на его начало и конец. В таком случае несложно превратить дек 
в дек с индексацией за $O(1)$ ($A[s + i]$).

Однако память у нас конечная, поэтому в некоторый момент нам может потребоваться больше, чем мы имеем, и тогда нам придётся перевыделить память и скопировать имеющиеся 
элементы в неё. В случае дека (пусть в данный момент его длина равна $n$), разумно будет выделить память размером $3n$ (имеющиеся ячейки, $n$ ячеек в начало и $n$ ячеек 
в конец). В этом случае нам удастся добиться добавления нового элемента за амортизированное $O(1)$, так как $\frac{O(n)}{n} = O(1)$, где $O(n)$~--- время, 
затрачиваемое на выделение, и $n$ ~--- количество шагов доследующего перевыделения.

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

Итак, предположим, что мы исчерпали свободную память, и к нам пришёл новый элемент на добавление. Мы, как 
и в прошлый раз, перевыделяем память (увеличим её размер вдвое), однако копировать в неё все старые 
элементы сразу не будем, а поступим следующим образом: каждый раз, когда к нам будет приходить элемент на 
добавление, будем добавлять в стек его и один элемент из <<старого>> стека.
	
\begin{center}
\includegraphics[height=120pt]{theory-02-02.jpg}
\end{center}

Таким образом, к моменту, когда новая память заполнится, в неё уже будут скопированы все элементы из старой.

Как выделять и освобождать память?
\begin{cppcode}
int *a;
a = new int[size]; // добавление
delete[] a; // освобождение НЕ ЗАБЫВАТЬ КВАДРАТНЫЕ СКОБКИ!!!
\end{cppcode}

Итого, наш вектор перевыделяет память так:
\begin{cppcode}
n *= 2
delete[] Old;
Old = New;
New = new int[n];
\end{cppcode}

Подобную идею можно использовать не только в векторе.

Можно реализовать дек, стек и очередь двусвязным (или односвязным для стека и очереди) списком. Этот способ проще описанного выше, однако теряется возможность обращения 
к элементу по индексу.

У стека последний элемент лежит в начале списка и указывает на более глубокий. У очереди добавление идёт в конец списка, нужно также хранить указатель на конец списка.
В языке С++ \cpp$std::deque$~--- дек с индексацией, а \cpp$std::queue$ и \cpp$std::stack$~--- без индексации. 

\section{Хеш-множество}

Хеш-множество (HashSet): Мы хотим иметь множество, уметь добавлять и удалять элементы, а также быстро искать их.

Научимся делать хеш-множество для маленьких чисел. Это можно сделать массивом \cpp$bool$, размер которого будет равен максимальному из хранимых в нём элементов.
\begin{Rem}
Из C++: быстрый массив из $N$ бит есть \cpp|std::bitset<N>|. Используется эквивалентно массиву, плюс умеет делать побитовые операции (\cpp@&, |, ^@). Устроен как массив 
целых чисел, только памяти использует меньше.
\end{Rem} 
Вспомним, что есть просто список (List): он умеет то же самое, но всё, кроме добавления, работает $O(n)$.

Однако N может принимать достаточно большие значения($N \leqslant 10^{18}$). В таком случае мы хотим хранить наши числа в массиве (массиве списков, так как возможны коллизии) 
длины М, где $M \leqslant 10^6$. Каждый элемент $x \in \left[0, N\right)$ будет лежать в списке, хранящемся в ячейке $i \in \left[0, M\right)$, вычисляемой по некоторому 
<<хорошему>> правилу. Если $i$ будут распределены равномерно, то примерное количество чисел в одной ячейке составит $\frac{n}{M}$ штук, где $n$ - количество элементов 
$x$.

Какое <<хорошее>> правило можно взять? Утверждается, что следующее правило окажется вполне подходящим:
$$
\begin{cases}
	i = x \bmod M\\
	M \text{ --- простое}
\end{cases}
$$
Для того, чтобы время поиска элемента множества оставалось $O(1)$, будем постоянно поддерживать выполнение
условия $\frac{n}{M} \leqslant C$, и если в какой-то момент количество элементов $n$ станет слишком большим и условие
перестанет выполняться, то изменим число М примерно в 2 раза(при этом М должно остаться простым).

Как же найти новый простой модуль? Идём вперёд и увеличиваем, пока не простое.
Время работы данного алгоритма составит $O(\sqrt{n} \log n)$, так как среднее расстояние между простыми числами равно логарифму.

В C++ и Java стандарнтые хешмножества удваиваются долго, за линию.

\section{Хеш-таблица}
Раньше мы хранили $х$~--- элементы множества. Теперь будем хранить пары $(x, y)$, где $х$~--- ключ, а $y$~--- значение,
которое мы сможем по этому ключу находить. Получилась хеш-таблица (HashTable). Как её сделать:
\begin{cppcode}
bitset<N> u; //присутствует ли ключ х в множестве
int y[N];    //значение по ключу, если есть
\end{cppcode}

Можно обойтись только вторым массивом и фиктивными элементами.

\section{Частичные суммы}
\begin{cppcode}
sum[0] = 0;
for (int i(0); i < n; ++i)
	sum[i + 1] = sum[i] + a[i]; 
\end{cppcode}
$$ \sum_{i=L}^{R-1} a_i = Sum[R] - Sum[L]$$

\section{Бинарный поиск}
Пусть есть отсортированный массив $a$. Научимся быстро понимать каждую из трёх следующих вещей: присутствует ли элемент в массиве, на какой позиции в массиве находится 
данный элемент(поиск), на какой позиции в массиве находится первый элемент, больший либо равный заданному. Для защиты можно в конец добавить фиктивный элемент, 
гарантированно больший всех. Каждая следующая задача решает все предыдущие; более того, код будет практически таким же. При этом первые два варианта реализуются 
хеш-таблицей ($Map[A[x]] = x \Lra x \text{ присутствует}$).

Для первых двух задач:
\begin{cppcode}
l = 0;
r = n - 1;
while (l <= r)
{
	m = (l + r) / 2;
	if (a[m] == x)
		return 1 // m;
	if (a[m] > x)
		r = m - 1;
	else
		l = m + 1;
}
\end{cppcode}

Для последней:
\begin{cppcode}
l = 0;
r = n - 1;
while (l <= r)
{
	m = (l + r) / 2;
	if (a[m] > x)
		r = m - 1;
	else
		l = m + 1;
}
return l;
\end{cppcode}

\section{Задачи}
\begin{enumerate}
\item Количество различных чисел [static]
\begin{itemize}
\item HashSet. Запихнём все, пробежимся. $O(n)$.
\item Sort. Посортируем, ищем количество различных соседей и прибавить единицу. $O(n \log n)$.
\end{itemize}
\item Количество различных чисел [dynamic, online]
\begin{itemize}
\item HashMap. Для каждого числа храним его количество $count$. Также храним количество разных чисел $result$. Если нам поступил запрос $Add$ и $count[x] = 0$, то 
увеличим $result$. $Del$ реализуем зеркально. $O(1)$.
\end{itemize}
\item Stack, Deque: [online] с удвоением, [offline] заранее выделяем, сколько надо.
\item Выделение памяти (Allocation). Нужны функции:
\begin{itemize}
\item \cpp|void* new(int size)|
\item \cpp|void delete(void *what)|
\end{itemize}
Есть полезные подслучаи:
\begin{itemize}
\item $n = const$~--- стек свободных ячеек. Возьмём себе место под стек, а оставшееся место режем по $n$ байт. Стек содержит указатели на все эти ячейки. Когда у нас 
просят $new$, возвращаем значение на вершине стека, $delete$~--- кладём указатель на освободившийся участок обратно в стек.\\
В современной реальности есть следующие размеры кешей: $4 KB < 4 MB < 4 GB < 4 TB$ (кеши процессора, оперативка, жёсткая память). При понижении уровня скорость 
падает в 10--20 раз. \\
Если списком: храним список из кусков $n + размерУказателя$ байт. Теперь всё шустрее с точки зрения кеширования, т.к. все операции происходят только в начале памяти.
\item Можно хранить указатель на начало свободной памяти, а при выделении памяти сдвигать его (на столько, сколько памяти у нас попросили). В таком случае можно 
запоминать, на сколько мы сдвинулись в последний раз, и тогда мы сможем освобождать последний выделенный участок памяти.
\end{itemize}
\end{enumerate}
\end{document}