Больше я смотрю на логику, лежащую в основе этой структуры данных, больше я заинтригован ею, а затем перехожу к ее реализации, которая устанавливает собственный уровень.
Это всего лишь вводное объяснение дерева Фенвика на простом примере.
Введение
Дерево Фенвика или двоичное индексированное дерево - это структура данных, которая может эффективно вычислять суммы префиксов и обновлять элементы.
Основная идея
Каждое целое число можно представить как сумму степеней двойки. Таким же образом можно рассчитать совокупную сумму как сумму наборов этой совокупной частоты.
Пусть сумма наборов этой совокупной частоты будет представлена массивом, обозначенным T.
T[4]=A[1]+A[2]+A[3]+A[4]
Если вы хотите вычислить совокупную сумму от A [1] до A [7], тогда
Кумулятивная сумма = T [7] + T [6] + T [4] {T [7] = A [7], T [6] = A [6] + A [5], T [4]] " = A [1] + A [2] + A [3] + A [4]}
Откуда мы получаем, что T [7], T [6] и T [4] будут вносить вклад в сумму префикса до 7?
7 представлен 111 в двоичном формате. Если вы сбросите последний установленный бит, мы получим 110, что даст 6. Опять же, если вы сбросите последний установленный бит, мы получим 100, что даст 4. Итак, это индексы, которые вносят вклад в сумму префикса до 7.
Как изолировать последний установленный бит?
Если «И» число с его двумя дополнениями, мы получим последний установленный бит числа, который мы можем вычесть из исходного числа, чтобы сбросить последний установленный бит числа. Как показано на изображении выше, 7 преобразуется в 6 после сброса последнего установленного бита.
х - = (х & -x); // Для сброса последнего бита, значение x которого равно 0
Теперь возникает вопрос, где каждое число в исходном массиве вносит свой вклад в массив T.
Обновить
A [1] вносит вклад в T [1], T [2], T [4], T [8] и т. Д. {В двоичном формате 1- ›1,10,100,1000}
A [3] вносит вклад в T [3], T [4], T [8] и т. Д. {В двоичном формате 3- ›11,100,1000}
A [5] вносит вклад в T [5], T [6], T [8] и т. Д. {В двоичном формате 5- ›101,110,1000}
Здесь, если мы присмотримся, мы увидим, что нам нужно добавить последний установленный бит к числу, чтобы перейти в то место, где он будет вносить следующий вклад.
х + = (х & -x); // Для добавления последнего установленного бита до тех пор, пока x не достигнет максимальной длины дерева или исходного массива.
Сложность времени
Сложность пространства: O (N) для объявления другого массива размером N
Сложность времени:
O (журнал N) для каждой операции (также обновление и запрос)
O (журнал N) для построения дерева (обновление дерева n раз)
Пример
Давайте напишем код для запроса суммы диапазона, используя дерево Фенвика.
Обновление дерева сумм префиксов
void update(int ind,int num){
while(ind<v.size()){
v[ind]+=num;
ind+=(ind & -ind); //Adding the last set bit
}
}
Запросы к дереву сумм префиксов
int getsum(int ind){
int sum=0;
while(ind>0){
sum+=v[ind];
ind-=(ind & -ind); //Unset the last set bit
}
return sum;
}
Строим дерево
for(int i=0;i<n;i++){
int num;
cin>>num;
update(i+1,num);
}
Получение суммы диапазона
while(t--){
int l,r;
cin>>l>>r;
cout<<getsum(r)-getsum(l-1)<<endl;
}
Подведение итогов
Бинарное индексированное дерево легко реализовать и занимает линейный объем памяти. Операция запроса и обновления занимает время O (logN).
Проблемы с практикой
Для отработки большего количества задач с этой удивительной структурой данных.
