Список являются одним из самых используемых типов данных в языке Python. Если все ваше знакомство со списками ограничивается массивами в Visual Basic или (не дай бог) datastore в Powerbuilder, возмите себя в руки для знакомства со списками в языке Python.

• Списки в языке Python похожи на массивы в языке Perl. Имена пееменных, хранящих массивы, в языке Perl всегда начинаются с символа @. Python не накладывает никаких дополнительных ограничений на имя переменных, в которых хранятся списки, интерпретатор сам определяет тип переменной.
  
• Списки в языке Python — нечто большее, чем массивы в Java (хотя вы можете использовать их в таком качестве, если это все, что вам требуется от жизни). Более близкой аналогией будет класс Vector, способный содержать произвольные объекты и динамически увеличиваться при добавлении новых элементов.
  

Пример 1.14. Определение списков

>>> li = ["a", "b", "mpilgrim", "z", "example"]
>>> li
['a', 'b', 'mpilgrim', 'z', 'example']
>>> li[0]
'a'
>>> li[4]
'example'

• Сначала мы определяем список из пяти элементов. Обратите внимание, что исходный порядок элементов сохраняется. Это не случайно, список является упорядоченным множеством элементов, перечисленных в квадратных скобках.
  
• Списки могут быть использованы в качестве массивов. Отсчет элементов всегда ведется от нуля, так что первый элемент непустого списка — li[0].
  
• Последний элемент списка из пяти элементо — li[4], так как отсчет ведется от нуля.
  

Пример 1.15. Отрицательные индексы

>>> li
['a', 'b', 'mpilgrim', 'z', 'example']
>>> li[-1]
'example'
>>> li[-3]
'mpilgrim'

• При использовании отрицательных индексов отсчет ведется с конца списка. Послединий элемент любого непустого списка можно получить, используя выражение li[-1].
  
• Если вас смущают отрицательные индексы, запомните простое правило: li[-n] == li[len(li) - n]. То есть, в нашем случае li[-3] == li[5 - 3] == li[2].
  

Пример 1.16. Срез

>>> li
['a', 'b', 'mpilgrim', 'z', 'example']
>>> li[1:3]
['b', 'mpilgrim']
>>> li[1:-1]
['b', 'mpilgrim', 'z']
>>> li[0:3]
['a', 'b', 'mpilgrim']

• Указав через двоеточие два индекса, вы можете получить подмножество элементов списка, называемое “срезом”. Получаемое значение является новым списком, содержащим все элементы исходного списка в том же порядке, начиная с первого индекса (здесь li[1]) до, но не включая, второго индекса (здесь li[3]).
  
• В операции среза также можно использовать отрицательные идексы. Если это поможет, считайте первый индекс соответствующим первому элементу, который вам нужен, и второй — первому элементу, который не нужен. Получаемое значение — все, что между ними находится.
  
• Нумерация элементов начинается с нуля, так что li[0:3] дает первые три элемента исходного списка.
  

Пример 1.17. Сокращения в записи среза

>>> li
['a', 'b', 'mpilgrim', 'z', 'example']
>>> li[:3]
['a', 'b', 'mpilgrim']
>>> li[3:]
['z', 'example']
>>> li[:]
['a', 'b', 'mpilgrim', 'z', 'example']

• Если первый индекс среза равен нулю, то его можно опустить. Аналогично можно опустить второй индекс, если он равен длине списка. То есть li[:3] дает такой же результат, как и li[0:3] в предыдущем примере.
  
• Обратите внимание на симметрию. Для данного списка из пяти элементов li[:3] дает первые три элемента и li[3:] — последние два. В самом деле, li[:n] всегда дает первые n элементов, а li[n:] — все остальное.
  
• Если опущены оба индекса, будут включены все элемента исходного списка. Но это не тот же список, это новый список с теми же элементами. Таким образом, li[:] позволяет создать копию списка.
  

Пример 1.18. Добавление элементов в список

>>> li
['a', 'b', 'mpilgrim', 'z', 'example']
>>> li.append("new")
>>> li
['a', 'b', 'mpilgrim', 'z', 'example', 'new']
>>> li.insert(2, "new")
>>> li
['a', 'b', 'new', 'mpilgrim', 'z', 'example', 'new']
>>> li.extend(["two", "elements"])
>>> li
['a', 'b', 'new', 'mpilgrim', 'z', 'example', 'new', 'two', 'elements']

• Метод append добавляет один элемент в конец списка.
  
• Метод insert вставляет один элемент в список. Целочисленный аргумент является индексом первого элемента, позиция которого изменится. Обратите внимание, что элементы списка могут быть не уникальными — после этой операции в списке содержится два элемента со значением "new", li[2] и li[6].
  
• Метод extend добавляет в конец элементы другого списка. В данном случае второй список содержит два элемента.
  

Пример 1.19. Поиск в списке

>>> li
['a', 'b', 'new', 'mpilgrim', 'z', 'example', 'new', 'two', 'elements']
>>> li.index("example")
5
>>> li.index("new")
2
>>> li.index("c")
Traceback (innermost last):
File "<interactive input>", line 1, in ?
ValueError: list.index(x): x not in list
>>> "c" in li
0

• Метод index находит первое вхождение элемента в списке и возвращает его индекс.
  
• index позволяет найти только первое вхождение элемента. В нашем списке строка "new" присутствует дважды (li[2] и li[6]), но метод index вернет индекс только первого — 2.
  
• Если указанный элемент в списке не найден, генерируется исключение. Такое поведение заметно отличается от поведения аналогичных средств в других языках, возвращающих какой-либо некорректный индекс. Генерация исключения более удобна, так как работа программы останавливается в месте возникновения ошибки, а не в момент использования некорректного индекса.
  
• Для проверки наличия элемента в списке используйте оператор in, возвращающий 1, если значение найдено, и 0, если в списке такого значения нет.
  

Python не имеет отдельного булева типа. В булевом контексте (например, в условии инструкции if), 0 является ложью, а все остальные сисла являются истиной. Аналогично и для других типов: пустая строка (""), список ([]) и словарь ({}) являются ложью, а все остальные строки, списки и словари — истиной.

Пример 1.20. Удаление элементов из списка

>>> li
['a', 'b', 'new', 'mpilgrim', 'z', 'example', 'new', 'two', 'elements']
>>> li.remove("z")
>>> li
['a', 'b', 'new', 'mpilgrim', 'example', 'new', 'two', 'elements']
>>> li.remove("new")
>>> li
['a', 'b', 'mpilgrim', 'example', 'new', 'two', 'elements']
>>> li.remove("c")
Traceback (innermost last):
File "<interactive input>", line 1, in ?
ValueError: list.remove(x): x not in list
>>> li.pop()
'elements'
>>> li
['a', 'b', 'mpilgrim', 'example', 'new', 'two']

• Метод remove удаляет из списка первый элемент с указанным значением.
  
• remove удаляет только один элемент. В данном случае строка "new" присутствует в списке дважды, но li.remove("new") удалит только первую.
  
• Если элемент с указанным значением в списке не найден, remove, как и index, генерирует исключение.
  
• Метод pop выполняет сразу два действия: удаляет последний элемент из списка и возвращает его. Этим он отличается от li[-1], возвращающего последний элемент, но не изменяющего список, и li.remove(value), изменяющего список, но не возвращающего элемент.
  

Пример 1.21. Применение операторов к спискам

>>> li = ['a', 'b', 'mpilgrim']
>>> li = li + ['example', 'new']
>>> li
['a', 'b', 'mpilgrim', 'example', 'new']
>>> li += ['two']
>>> li
['a', 'b', 'mpilgrim', 'example', 'new', 'two']
>>> li = [1, 2] * 3
>>> li
[1, 2, 1, 2, 1, 2]

• С помощью оператора + можно “склеивать” списки. list = list + otherlist эквивалентно list.extend(otherlist), но при этом создается новый список, в то время как extend изменяет существующий.
  
• Python поддерживает операцию +=. li += ['two'] полностью эквивалентно li.extend(['two']). Операция += работает для списков, строк, чисел и может быть переопределена для классов (более подробно о классах читайте в главе 3).
  
• Оператор * размножает элементы списка. li = [1, 2] * 3 эквивалентно li = [1, 2] + [1, 2] + [1, 2].
  

Сборка мусора
В программировании, сборка мусора — одна из форм автоматического управления памятью. Специальный код, называемый сборщиком мусора (garbage collector), в определённые моменты времени пытается освободить память, использованную объектами, которые уже не будут востребованы приложением — то есть производит сборку мусора.

Проблемы управления временем жизни объектов

В любом языке, допускающем создание объектов в динамической памяти, потенциально возможные две проблемы: висячие ссылки (англ. dangling pointer) и утечки памяти (англ. memory leak). Обе эти проблемы возникают из-за неправильного управления временем жизни объектов, создаваемых в динамической памяти.

Висячие ссылки

Предположим, есть два указателя (ссылки) на один и тот же объект. Если удалить объект через первый указатель, но не изменить значение второго, то второй будет продолжать указывать на уже удалённый объект. Память, занимаемая ранее объектом, может быть передана операционной системе и стать недоступной для программы или быть использована для размещения нового объекта в той же программе. В первом случае попытка обратиться по второму указателю приведёт к срабатыванию механизма защиты памяти и аварийной остановке программы, а во втором - к непредсказуемым последствиям.

Утечки памяти

Предположим, объект был создан и его адрес был записан в указатель. Затем этому указателю присвоили новое значение, не удалив перед этим объект и не присвоив его адрес другому указателю. В результате в программе не осталось ни одного указателя, по которому можно перейти к объекту или удалить объект. Такая ситуация называется утечкой памяти. Утечки памяти приводят к постепенному увеличению потребляемого программой объема памяти, и если программа работает долго, она может через достаточно большое время затормозить работу системы или исчерпать доступный объем адресного пространства (и завершиться с ошибкой).

Способы управления памятью

Сборка мусора часто противопоставляется ручному управлению памятью, при котором программист явно указывает, когда и какие области памяти надо освободить. Однако есть языки, в которых используется комбинация двух методов управления памятью, равно как есть и другие технологии решения той же фундаментальной проблемы (например, en:region inference).

По сравнению с ручным управлением памятью, сборка мусора безопаснее, поскольку она предотвращает утечки памяти и возникновение висячих ссылок, а также упрощает сам процесс программирования. Однако во многих случаях системы со сборкой мусора демонстрируют меньшую эффективность, как по скорости, так и по объёму используемой памяти. Кроме освобождения памяти, многие сборщики мусора способны также дефрагментировать (уплотнять) объекты в памяти системы, перемещая их так, чтобы они занимали сплошную область памяти, что благоприятно отражается на производительности системы.

Некоторые языки программирования требуют использования механизма сборки мусора в соответствии со своей спецификацией (Java, C#), другие — по причинам эффективности реализации (например, формальные языки для лямбда-исчисления) — эти языки называются языками со сборкой мусора. Многие языки со сборкой мусора не имеют возможностей для явного ручного удаления объектов (например, оператора delete), благодаря чему возникновение висячих ссылок исключается в принципе, а сборщик мусора лишь занимается удалением объектов, на которые нет ссылок из программы.

Базовые принципы работы сборщика мусора:

1. на время работы сборщика мусора выполнение программы останавливается
2. определение объектов программы, которые в будущем не будут использоваться;
3. освобождение памяти, занимаемой этими объектами.

Хотя в общем случае невозможно точно определить момент, когда объект был использован в последний раз и больше не нужен, сборщики мусора используют консервативные оценки, позволяющие определить, что в будущем объект уже не будет использоваться. Например, если в системе нет больше ссылок на данный объект — то он больше не может быть использован программой. Этот критерий используется большинством современных сборщиков мусора.
Отслеживающие сборщики мусора

Сборщики мусора этого типа отслеживают, какие объекты являются достижимыми (или потенциально достижимыми) и затем удаляют из памяти все остальные.

Достижимость объекта

Неформально можно задать следующее рекурсивное определение достижимого объекта:

* Определённое множество объектов считается достижимым изначально. Такие объекты называются корневыми. Обычно в их число включают все глобальные переменные и объекты, на которые есть ссылки в стеке вызовов.
* Любой объект, на который есть ссылка из достижимого объекта тоже считается достижимым. Исключение составляют слабые ссылки.

Такое определение не является наилучшим. Оптимальнее было бы считать недостижимым объект, к которому в процессе дальнейшей работы программы не будет ни одного обращения. Однако определение таких объектов можно свести к неразрешимой задаче об останове. Для этого достаточно предположить, что некоторый объект X будет использован в том и только в том случае, если успешно завершится программа P.

Как только определено множество недостижимых объектов, сборщик мусора может освободить память, занимаемую ими, и оставить остальное как есть. Также можно переместить все или часть оставшихся объектов в другие области памяти, обновив вместе с этим все ссылки на них. Эти два варианта реализации называются, соответственно, перемещающим и неперемещающим.

Обе стратегии имеют как достоинства, так и недостатки. Недостатком перемещающего сборщика является то, что при каждом выполнении цикла сборки мусора может потребоваться переместить достаточно большие объёмы данных. Тем не менее, этот недостаток может быть скомпенсирован тем, что

* На этапе сборки мусора можно выполнить дефрагментацию памяти.
* Перемещение позволяет использовать чрезвычайно простой и быстрый (O(1)) алгоритм выделения памяти. Для этого достаточно подвинуть объекты так, чтобы разделить всю память на две большие области — занятую и свободную, и хранить указатель на их границу. Тогда для выделения новой памяти достаточно будет лишь переместить эту границу, вернув кусок из начала свободной памяти.
* Объекты, поля которых используются совместно, можно разместить в памяти недалеко друг от друга. Тогда они вероятнее окажутся в кэше процессора одновременно, что уменьшит количество обращений к относительно медленной ОЗУ.

Ещё один недостаток перемещающего сборщика заключается в том, что он должен уследить за всеми ссылками на объект, чтобы иметь возможность изменить их при перемещении. Для работы с кодом, который не позволяет этого делать (такой код называется инородным (foreign) в традиционной терминологии или неуправляемым в терминологии Microsoft), используются различные приёмы. Например, pinning — блокировка объекта, запрещающая его перемещение во время сборки мусора.

Управление памятью под ответственностью программиста

В языке C++ (именно на его примере рассмотрим системы, где ответственность за своевременное освобождение блоков памяти лежит на программисте) существуют предусмотренные стандартом C++, а также перешедшие "в наследство" от C средства выделения и освобождения памяти. Кроме того, каждая платформа предоставляет свои средства управления памятью (как правило, стандартные языковые средства как раз к ним и обращаются, но у программиста есть возможность обратиться к ним непосредственно). Проблема этих систем и языков (в том числе C++) состоит в том, что программист сам отвечает за своевременное освобождение блоков памяти после того, как в них отпадает необходимость - для этого тоже есть специальные функции. Если программист забудет освободить блок, впоследствии может возникнуть нехватка памяти - виртуальное адресное пространство процесса "забьется" и свободного места не останется, хотя в то же время в памяти будут присутствовать блоки, которые фактически не используются.

Рассмотрим коротко средства управления памятью.

Оператор new очень удобен - он не требует указания размера блока, который нужно выделить. Размер определяется компилятором автоматически исходя из типа, который указывается после ключевого слова new. Кроме вызова самой функции выделения памяти происходит еще и вызов конструктора объекта, если указан объектный тип. Синтаксис вызова оператора имеет несколько вариантов, рассмотрим наиболее часто употребляемый:

new Type (parameters)

где Type - тип создаваемого объекта, на основе которого компилятор автоматически определит требуемый для него объем памяти;

parameters - необязательный список параметров, который будет передан конструктору объекта. В случае отсутствия списка параметров скобки указывать необязательно.

Функция malloc, доставшаяся языку C++ в наследство от C, требует указания необходимого количества байт и не производит кроме собственно выделения памяти никаких дополнительных действий.

Функции операционной системы Windows - LocalAlloc и GlobalAlloc - считаются устаревшими, хотя и поддерживаются в целях совместимости. Современным приложениям рекомендуется пользоваться HeapAlloc, а также VirtualAlloc, которая, помимо выделения памяти, поддерживает операцию резервирования памяти и выделения зарезервированной памяти.

Соответственно, средства освобождения памяти следующие.

Оператор delete освобождает занятый приложением блок, но перед этим вызывает деструктор объекта, если переменная объектного типа. Ничего, кроме параметра, содержащего адрес удаляемого блока, передавать не надо.

Функция free () освобождает выделенный с помощью malloc () блок. Следует передать адрес блока.

Функции Windows по освобождению памяти называются LocalFree, GlobalFree, HeapFree и VirtualFree.

Объясню суть проблемы такого управления памятью подробнее. Допустим, программисту нужно в цикле копировать файлы. Для этого он выделяет блок памяти необходимого размера, читает туда содержимое файла-источника, затем пишет содержимое блока в файл-приемник. Допустим теперь, что перед выходом из цикла человек забыл освободить выделенный блок. Начинается следующая итерация цикла, и происходит новое выделение памяти. Переменная, которая раньше содержала адрес первого блока, содержит теперь новый адрес - таким образом, адрес первого блока теряется! Значит, если вовремя не освободить выделенную память, есть вероятность, что адрес этого блока будет навсегда "забыт" приложением, и оно никогда не сможет его освободить.

Вообще-то, по завершении приложения операционная система просто полностью уничтожает виртуальное адресное пространство процесса, так что об этом, казалось бы, беспокоиться даже не стоит - память освободится автоматически при окончании работы программы. Однако, как упоминалось выше, неосвобожденные блоки будут накапливаться, а доступная для выделения свободная память будет заканчиваться, и это может привести к ситуации, когда система откажет вам в очередном выделении памяти. Особенно эта ситуация вероятна тогда, когда программист забывает об освобождении в цикле, тем более если тот имеет много итераций.

Кроме очевидного преимущества, у системы сборки мусора есть свои подводные камни. В этих системах невозможно или сложно реализовать "ручные" механизмы выделения и освобождения памяти - к примеру, если на C++ вы можете с легкостью запросить память у операционной системы огромным куском, а внутри этого большого "куска" реализовать свои механизмы выделения/освобождения памяти, перегрузив операторы new и delete, вы теоретически сможете путем ручного управления памятью ускорить работу своего приложения (если, конечно, сможете придумать алгоритм, более оптимальный, чем стандартные), то в таких языках и средах вы этого сделать не сможете. А стандартные методы освобождения и выделения приходится иногда переписывать - например, если вы хотите хранить данные в файле и использовать отображение файлов на память. Другой подводный камень - система сборки мусора может физически переместить объект (естественно, поскольку адрес объекта изменился, все ссылки на него стали недействительными - их надо исправить, и это дело системы сборки мусора). Таким образом, вы не можете "доверять" адресу переменной (если вообще есть возможность его получить), так как он непостоянен. Кроме того, чтобы у сборщика мусора была возможность перемещать объекты физически, объект должен содержать не просто счетчик ссылок, а список самих ссылок, что увеличивает расходы (как расход памяти, так и ресурс времени) на содержание объектов.

Дерево отрезков

Дерево отрезков - структура данных, которая позволяет реализовать за O (log N) операции следующего типа: нахождение суммы/минимума элементов массива в заданном отрезке (A[L..R], где L и R - это параметры запроса), изменение одного элемента массива, изменение/прибавление элементов на отрезке (A[L..R]). При этом объём дополнительно используемой памяти составляет O (N), или, если быть точным, не более 4 N.
Описание

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

Построим бинарное дерево T следующим образом. Корень дерева будет храниться в элементе T[1]. Он будет содержать сумму элементов A[0..N-1], т.е. всего массива. Левый сын корня будет храниться в элементе T[2] и содержать сумму первой половины массива A: A[0..N/2], а правый сын - в элементе T[3] и содержать сумму элементов A[N/2+1..N-1]. В общем случае, если T[i]-ый элемент содержит сумму элементов с L-го по R-ый, то его левым сыном будет элемент T[i*2] и содержать сумму A[L..(L+R)/2], а его правым сыном будет T[i*2+1] и содержать сумму A[(L+R)/2+1..R]. Исключение, разумеется, составляют листья дерева - вершины, в которых L = R.

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

Рассмотрим теперь операцию суммы на некотором отрезке [L; R]. Мы встаём в корень дерева (i=1), и рекурсивно движемся вниз по этому дереву. Если в какой-то момент оказывается, что L и R совпадают с границами отрезка текущего элемента, то мы просто возвращаем значение текущего элемента T. Иначе, если отрезок [L; R] целиком попадает в отрезок левого или правого сына текущего элемента, то мы рекурсивно вызываем себя из этого сына и найденное значение возвращаем. Наконец, если отрезок [L; R] частично принадлежит и отрезку левого сына, и отрезку правого сына, то делим отрезок [L; R] на два отрезка [L; M] и [M+1; R] так, чтобы первый отрезок целиком принадлежал отрезку левого сына, а второй отрезок - отрезку правого сына, и рекурсивно вызываем себя и от первого, и от второго отрезков, возвращая сумму найденных сумм. В итоге вся операция суммирования работает за O (log N).

Теперь рассмотрим операцию изменения значения некоторого элемента с индексом K. Будем спускаться по дереву от корня, ища тот лист, который содержит значение элемента A[K]. Когда мы найдём этот элемент, просто изменим соответствующее значение в массиве T и будем подниматься от текущего элемента обратно к корню, пересчитывая текущие значения T. Понятно, что таким образом мы изменим все значения в дереве, которые нужно изменить. Итого асимптотика O (log N).

Наконец, рассмотрим операцию изменения на отрезке. Для реализации этой операции нам понадобится немного модифицировать дерево. Пусть каждый элемент дерева, помимо суммы, будет содержать значение Val[i]: если все элементы массива A в текущем отрезке равны друг другу, то Val[i] будет содержать это значение, а иначе он будет содержать некое значение "неопределённость". Изначально его можно просто заполнить значениями "неопределённость". А при выполнении операции изменения на отрезке мы будем спускаться по дереву, как в вышеописанном алгоритме суммирования, и если в какой-то момент L и R совпали с границами текущего отрезка, то мы присвоим Val[i] новое значение, которое мы хотим записать. Понятно, что теперь надо будет модифицировать операцию суммирования - если она в какой-то момент встречает Val[i], отличное от "неопределённости", то она прекращает спуск по дереву и сразу возвращает нужное значение - действительно, результат уже определён значением Val[i], а вот если мы продолжим спуск, то уже будем считывать неправильные, старые значения.

Операция прибавления на отрезке реализуется подобным образом, но несколько проще. В каждом элементе мы храним Add[i] - значение, которое нужно прибавить ко всем элементам этого отрезка. Операция прибавления на отрезке будет модифицировать эти значения, а операция суммирования - просто прибавлять к ответу все встретившиеся значения Add.

long long sum (int l, int r, int i = 1, int tl = 0, int tr = n-1) {
if (l == tl && r == tr)
return t[i];
int m = (l + r) / 2;
if (r <= m)
return sum (l, r, i*2, tl, m);
if (l > m)
return sum (l, r, i*2+1, m+1, tr);
return sum (l, m, i*2, tl, m) + sum (m+1, r, i*2+1, m+1, tr);
}

void update (int pos, int newval, int i = 1, int l = 0, int r = n-1) {
if (l == r)
t[i] = newval;
else {
int m = (l + r) / 2;
if (i <= m)
update (pos, newval, i*2, l, m);
else
update (pos, newval, i*2+1, m+1, r);
t[i] = t[i*2] + t[i*2+1];
}
}

материал: http://maximal.hocomua.ru/segment_tree.htm

Дерево Фенвика

Дерево Фенвика - это структура данных, дерево на массиве, обладающее следующими свойствами:

1) позволяет вычислять значение некоторой обратимой операции G на любом отрезке [L; R] за время O (log N);

2) позволяет изменять значение любого элемента за O (log N);

3) требует O (N) памяти, а точнее, ровно столько же, сколько и массив из N элементов;

4) легко обобщается на случай многомерных массивов.

Наиболее распространённое применение дерева Фенвика - для вычисления суммы на отрезке, т.е. функция G (X1, ..., Xk) = X1 + ... + Xk.

Дерево Фенвика было впервые описано в статье "A new data structure for cumulative frequency tables" (Peter M. Fenwick, 1994).
Описание

Для простоты описания мы предполагаем, что операция G, по которой мы строим дерево, - это сумма.

Пусть дан массив A[0..N-1]. Дерево Фенвика - массив T[0..N-1], в каждом элементе которого хранится сумма некоторых элементов массива A:

Ti = сумма Aj для всех F(i) <= j <= i, где F(i) - некоторая функция.

Определим значение F(X) следующим образом. Рассмотрим двоичную запись этого числа и посмотрим на его младший бит. Если он равен нулю, то F(X) = X. Иначе двоичное представление числа X оканчивается на группу из одной или нескольких единиц. Заменим все единицы из этой группы на нули, и присвоим полученное число значению функции F(X).

Этому довольно сложному описанию соответствует очень простая формула:

F(X) = X & (X+1), где & - это операция побитового логического "И".

Нам осталось только научиться быстро находить такие числа j, для которых F(j) <= i <= j.

Однако нетрудно убедиться в том, что все такие числа j получаются из i последовательными заменами самого правого (самого младшего) нуля в двоичном представлении. Например, для i = 10 мы получим, что j = 11, 15, 31, 63 и т.д.

Как ни странно, такой операции (замена самого младшего нуля на единицу) также соответствует очень простая формула:

H(X) = X | (X+1), где | - это операция побитового логического "ИЛИ".

int sum (int r)
{
int result = 0;
for (; r >= 0; r = (r & (r+1)) - 1)
result += t[r];
return result;
}

void inc (int i, int delta)
{
for (; i < n; i = (i | (i+1)))
t[i] += delta;
}

int sum (int l, int r)
{
return sum ® - sum (l-1);
}

Функция sum работает следующим образом. Вместо того чтобы идти по всем элементам массива A, она движется по массиву T, делая "прыжки" через отрезки там, где это возможно. Сначала она прибавляет к ответу значение суммы на отрезке [F®; R], затем берёт сумму на отрезке [F(F®-1); F®-1], и так далее, пока не дойдёт до нуля.

Функция inc движется в обратную сторону - в сторону увеличения индексов, обновляя значения суммы Tj только для тех позиций, для которых это нужно, т.е. для всех j, для которых F(j) <= i <= j.

материал: http://maximal.hocomua.ru/Fenwick_tree.htm

Свя́занный спи́сок — это структура данных, в которой объекты расположены в линейном порядке. Однако, в отличие от массива, в котором этот порядок определяется индексами, порядок в связанном списке определяется указателями на каждый объект. Связанные списки обеспечивают простое и гибкое представление динамических множеств и поддерживают все операции (возможно, недостаточно эффективно).

Линейный связанный список

Односвязный список

В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента невозможно.

Двусвязный список

По двусвязному списку можно передвигаться в любом направлении — как к началу, так и к концу. В этом списке проще производить удаление и перестановку элементов, т.к. всегда известны адреса тех элементов списка, указатели которых направлены на изменяемый элемент.

Xor-связанный список

XOR-связанный список — структура данных, похожая на обычный двухсвязный список, однако в каждом элементе хранящая только ОДИН адрес — результат выполнения операции XOR над адресами предыдущего и следующего элемента списка. Для того, чтобы перемещаться по списку, необходимо взять два последовательных адреса и выполнить над ними операцию исключающего ИЛИ, которая и даст реальный адрес следующего элемента. В сравнении с обычным двусвязным списком, XOR список расходует в два раза меньше памяти для хранения связей между элементами. Из недостатков можно упомянуть более сложную реализацию, невозможность использования стандартного сборщика мусора, затруднения при отладке программы. Употребляется довольно редко, так как существуют хорошие альтернативы, как, например, развёрнутый связанный список.

Кольцевой связанный список

Разновидностью связанных списков является кольцевой (циклический, замкнутый) список. Он тоже может быть односвязным или двусвязным. Последний элемент кольцевого списка содержит указатель на первый, а первый (в случае двусвязного списка) — на последний.

Список с пропусками

Список с пропусками - разновидность упорядоченного списка, позволяющий быстро находить любой его элемент. В обычном упорядоченном списке для поиска необходимо просматривать все элементы по порядку, таким образом поиск произвольного элемента занимает в среднем n/2 операций, где n - количество элементов в списке. Список с пропусками содержит специальные дополнительные указатели, позволяющие "перескочить" через определённое количество элементов, таким образом можно реализовать более быстрый поиск, занимая всего O(log1/p n / p) операций, где p - константа.

Развёрнутый связанный список

Развёрнутый связанный список — список, каждый физический элемент которого содержит несколько логических (обычно в виде массива, что позволяет ускорить доступ к отдельным элементам).

Позволяет значительно уменьшить размер памяти и увеличить производительность по сравнению с обычным списком. Особенно большая экономия памяти достигается при очень малом размере логических элементов и большом их количестве — так, односвязный список из 10000 четырёхбайтовых целых чисел при четырёхбайтовой же адресации памяти занимает 10000 дополнительных байт под адреса, если же обьединить числа в массивы по 100, расход памяти упадёт до 100 байт.

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

Достоинства
• лёгкость добавления и удаления элементов
• размер ограничен только объёмом памяти компьютера и разрядностью указателей
Недостатки
• сложность определения адреса элемента по его индексу (номеру) в списке
• на поле указателей расходуется дополнительная память (в массивах, например, указатели не нужны)
• работа со списком медленнее, чем с массивами, так как к любому элементу списка можно обратится, только пройдя все предшествующие ему элементы

Стек

Стек (англ. stack — стопка) — структура данных с методом доступа к элементам LIFO (Last In — First Out, последним пришел — первым вышел). Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно взять верхнюю.

Добавление элемента, называемое также проталкиванием (push), возможно только в вершину стека (добавленный элемент становится первым сверху), выталкивание (pop) — также только из вершины стека, при этом второй сверху элемент становится верхним.

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

Очередь

Очередь — структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, First In — First Out). Добавление элемента (принято обозначать словом enqueue) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть dequeue, при этом выбранный элемент из очереди удаляется).

Способы реализации очереди

Существуют два основных способа реализации очереди на языке программирования.

Первый способ представляет очередь в виде массива и двух целочисленных переменных start и end.

Переменные start и end указывают на голову и хвост очереди соответственно. При добавлении элемента в очередь переменная end уменьшается на 1 и в q[end] записывается новый элемент очереди. Если значение end становится меньше 1, то мы как бы циклически обходим массив и значение переменной становится равным n. Извлечение элемента из очереди производится аналогично (при извлечении элемента q[start] из очереди, переменная start уменьшается на 1).

Преимущества данного метода: возможна незначительная экономия памяти по сравнению со вторым способом; проще в разработке.
Недостатки: ограничение на максимальное количество элементов в очереди размером массива (n).

Второй способ основан на работе с динамической памятью. Очередь представляется в качестве линейного списка, в котором добавление\удаление элементов идет строго с соответствующих его концов.

Преимущества данного метода: размер очереди ограничен лишь объемом памяти.
Недостатки: сложнее в разработке.

Очереди в различных языках программирования

Практически во всех развитых языках программирования реализованы очереди. В CLI для этого предусмотрен класс System.Сollections.Queue с методами Enqueue и Dequeue. В STL также присутствует класс queue<>, определённый в заголовочном файле queue. В нём используется та же терминология (push и pop), что и в стеках.

Применение очередей

Очередь в программировании используется, как и в реальной жизни, когда нужно совершить какие-то действия в порядке их поступления, выполнив их последовательно. Примером может служить организация событий в Windows. Когда пользователь оказывает какое-то действие на приложение, то в приложении не вызывается соответствующая процедура (ведь в этот момент приложение может совершать другие действия), а ему присылается сообщение, содержащее информацию о совершенном действии, это сообщение ставится в очередь, и только когда будут обработаны сообщения, пришедшие ранее, приложение выполнит необходимое действие.

Дек

Дек - особый вид очереди. Дек (от англ. deq - double ended queue,т.е очередь с двумя концами) - это такой последовательный список, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка. Частный случай дека - дек с ограниченным входом и дек с ограниченным выходом. Логическая и физическая структуры дека аналогичны логической и физической структуре кольцевой FIFO-очереди. Однако, применительно к деку целесообразно говорить не о начале и конце, а о левом и правом конце.

Операции над деком:

включение элемента справа;
включение элемента слева;
исключение элемента справа;
исключение элемента слева;
определение размера;
очистка.

Физическая структура дека в статической памяти идентична структуре кольцевой очереди. Динамическая реализация является очевидным объединением стека и очереди.

Задачи, требующие структуры дека, встречаются в вычислительной технике и программировании гораздо реже, чем задачи, реализуемые на структуре стека или очереди. Как правило, вся организация дека выполняется программистом без каких-либо специальных средств системной поддержки.

Примером дека может быть, например, некий терминал, в который вводятся команды, каждая из которых выполняется какое-то время. Если ввести следующую команду, не дождавшись, пока закончится выполнение предыдущей, то она встанет в очередь и начнет выполняться, как только освободится терминал. Это FIFO очередь. Если же дополнительно ввести операцию отмены последней введенной команды, то получается дек.