Сложность и поиск

Сложность в нотации O показывает, как растёт время с ростом входа. Линейный поиск — O(n), бинарный поиск — O(log n), но только по отсортированному массиву. Хорошая сортировка — O(n log n). Префиксные суммы pre[i] = a[1] + … + a[i] дают сумму на отрезке за O(1): pre[r] − pre[l−1].