Почему функция RangeUpdate () для дерева Фенвика не дает правильного вывода?

Я реализовал Fenwick Tree (BIT) с функцией RangeUpdate () для обновления (приращения) каждого элемента в диапазон на некоторое значение. Все остальные функции, которые я реализовал, работают нормально, кроме этого. Он не увеличивает каждый элемент на указанное значение. Что не так с этой функцией? Вот мой код:

#include <iostream>

using namespace std;

int BIT[100000];

void initBIT(int *Array,int Size)
{
for(int i=1; i<=Size; i++)
{
int Add=Array[i-1];
int j=i;
while(j<=Size)
{
BIT[j] += Add;
j += (j & (-j));
}
}
}

int SumQuery(int Index)
{
int Sum=0;
while(Index>0)
{
Sum += BIT[Index];
Index -= Index & (-Index);
}
return Sum;
}

int RangeSumQuery(int i,int j)
{
return SumQuery(j)-SumQuery(i-1);
}

void Update(int Index, int Value, int Size)
{
while(Index<=Size)
{
BIT[Index] += Value;
Index += Index & (-Index);
}
}

void RangeUpdate(int i, int j, int Value, int Size)
{
Update(i,Value,Size);
Update(j+1,-Value,Size);
}

int main()
{
ios::sync_with_stdio(false);

int a[10]={4,1,6,7,2,8,9,2,5,3};

initBIT(a,10);
cout<<SumQuery(4)<<endl;   //Output: 18; which is correct.
cout<<RangeSumQuery(3,5)<<endl;   //Output: 15; which is correct.
RangeUpdate(1,4,1,10);           //Tried to increment every element from range 1 to 4 by 1.
cout<<SumQuery(4)<<endl;       //Output: 19; which is incorrect. Output should be 22. Every element from range 1 to 4 didn't get incremented by 1.

return 0;
}

Почему функция RangeUpdate(int i, int j, int Value, int Size) не обновлять каждый элемент в диапазоне?

1

Решение

Задача ещё не решена.

Другие решения


По вопросам рекламы [email protected]