\Section{Структуры данных}{18 сентября}{Екатерина Кощенко}

\Subsection{Частичные суммы}

Partial sums, Префиксные суммы. В C++ лежит в <numeric>.
\begin{code}
	Build psum:
	psum[0] = 0;
	for i = 0..n
		psum[i+1] = psum[i] + a[i]; //O(n)
		
	Get [L..R]:
	return psum[R+1] - psum[L];
\end{code}

\Subsection{Бинарный поиск по отсортированному массиву}

\THE{Проверка на наличие}\\
Хотим узнать, есть ли элемент в массиве. Возвращаем его индекс, если есть, -1~--- если нет.
\begin{code}
	l = 0; r = n - 1;
	while (l <= r){
		m = (l + r) / 2;
		if (a[m] == x) return m;
		if (a[m] > x) r = m - 1;
		else l = m + 1;
	}
	return -1;
\end{code}

\THE{Поиск ближайшего}\\
Хотим узнать, на какой позиции находится первый элемент, больший или равный данному.
\begin{code}
	l = -1; r = n;
	while (l <= r){
		m = (l + r) / 2;
		if (a[m] > x) r = m;
		else l = m;
	}
	return l;
\end{code}

\Subsection{Два указателя}\\
\THE{Интересные слова}
\begin{enumerate}
	\item \textit{Offline}.
	Запросы поступают <<пачками>>, ответ дается на все сразу. Время работы = время на обработку всех запросов.
	\item \textit{Online}.
	Запросы поступают по одному, ответ дается сразу. Время работы = время на обработку одного запроса.
\end{enumerate}

\THE{Метод двух указателей}\\
Даны два массива A и B. Про каждый эл-т массива A сказать, есть ли он в B.
\begin{code}
	sort (A); sort(B); A[n] = INF; i = 0;
	for j = 0..B.size()-1{
		while (A[i] < B[j]) i++;
		if (A[i] == B[j]) cout << "yes";
	}
\end{code}
Это Offline решение. У задачи есть и Online решение.
\begin{code}
	sort(A);
	for j = 0..B.size()-1{
		BS(A, B[j]);
	}
\end{code}
Что изменилось: сортируем теперь только один массив, вместо метода двух указателей используем бинпоиск (BS).

\Subsection{Хеш-таблица}\\
Хотим такую структуру данных, в которой за $\mathcal O(1)$ будем уметь добавлять и удалять элементы, искать их. В C++ есть структуры HashSet и HashMap, которые удовлетворяют этим условиям. Различия: у HashMap ключ не обязательно дожен быть int, он может быть любого типа.
\begin{center}
	unordered\_set<int>\\
	unordered\_map<string, int>
\end{center}
Чтобы они быстрее работали, стоит заранее выделить им какой-то объем памяти (лучше максимальный, какой может потребоваться). А если еще написать a.rehash(N); то это ускорит процесс на 10\%.

\THE{Хеш-таблица на списках}
Будем хранить наши $m$ элементов в $n$ списках. При хорошей хеш-функции длины списков будут примерно $\frac{n}{m}$, то есть все операции будут выполняться за $\frac{n}{m}$. А так как мы хотим $\mathcal O(1)$, то m должен быть примерно равен n. Пример хеш-функции: $i = x \% m$, где $i$ - номер списка, $x$ - элемент,к оторый хотим добавить, а $m$ - простое число, не сильно большее $n$. Если нам $n$ заранее неизвестно, то может случиться ситуация, когда в один список запишется слишком эл-тов, время работы сильно ухудшится. Чтобы этого избежать, нужно время от времени удваивать кол-во списков и перезаписывать уже умеющиеся эл-ты в новую хештаблицу.\\
\pagebreak

\textit{\textbf{Функция поиска в хеш-таблице на списках}}
\begin{code}
	struct Node{
		Node* Next;
		int x;
	}
	
	Node* h[m];
	
	Node* Find(int x){
		Node* v = &h[x % m];
		while (v&&v -> x != x)
		v = v -> next;
		return v;
	}
\end{code}
\textit{\textbf{Добавление}}
\begin{code}
	if (finx(x) == 0)
	h[x % m] = {h[x % m], x}
\end{code}
\textit{\textbf{Удаление}}
\begin{code}
	find(x) -> x = -1;
\end{code}

\THE{Хеш-таблица с открытой адресацией}
Все элементы хранятся непосредственно в хеш-таблице, без использования связных списков. Когда мы попытаемся добавить элемент в уже занятую ячейку, то будем последовательно рассматривать следующие после нее ячейки, пока не найдем пустую. Туда и запишем наш эл-т. Опять-таки может возникнуть ситуация, когда хеш-таблица окажется полностью заполненной. И это тоже решается увеличением размера таблицы и перезаписью эл-тов.
\begin{code}
	int n[m];
	fill(h, h+m, -1); // `заполняем хеш-таблицу размера m - 1`
	
	h[Find(x)] = x; // `добавляем эл-т x, если его еще нет`
	h[Find(x)] = -2; // `удаляем x`
	
	int Find(int x){
		int i = x % m;
		while (h[i] != -1 && h[i] != x)
			i = (i + 1) % m;
		return i;
	}
\end{code}