Я реализовал 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)
не обновлять каждый элемент в диапазоне?
Задача ещё не решена.