На этой неделе проходили соревнования 2011 TopCoder Open. Проходит сие мероприятие во Флориде, с 26 сентября. Спонсорами мероприятия выступают: facebook, intel, MemSQL, Mashery. Соревнования проводятся в 6 категориях, это Algorithm, Marathon, Design, Development, Studio, Mod Dash.

Здравствуй, Хабрахабр. Сейчас я хочу рассказать о такой структуре данных как дерево Фенвика. Впервые описанной Питером Фенвиком в 1994 году. Данная структура похожа на дерево отрезков, но проще в реализации.

Что это?

Дерево Фенвика — это структура данных, дерево на массиве, которая обладает следующими свойствами:
• позволяет вычислять значение некоторой обратимой операции F на любом отрезке [L; R] за логарифмическое время;
• позволяет изменять значение любого элемента за O(log N);
• требует памяти O(N);