Ошибка сегментации в дереве Фенвика (Binary Index Tree)

Я понял Fenwick Tree, но когда я пытаюсь найти сумму по сегменту, возникает ошибка сегментации 11.

#include <vector>
#include <iostream>
using namespace std;class Fenwick{
public:
Fenwick();
int sum(int l, int r);
void update(int pos, int value);
void print(int i);
private:
vector<int> fentr;
int sum(int i);
};
Fenwick::Fenwick(){
}

void Fenwick::print(int i){
cout<<fentr[i];
}
int Fenwick::sum(int l, int r){
return sum(r)-sum(l-1);
}
int Fenwick::sum(int i){
int result=0;
// while(i>=0){
//  result+=fentr[i];
//  i=(i&(i+1))-1;
// }
for(int j=i; j>=0; j=(i&(i+1))-1){
result+=fentr[j];
}
return result;
}

void Fenwick::update(int pos, int value){
while (pos<fentr.size()){
fentr[pos]+=value;
pos=pos | (pos+1);
}
}int main(){
Fenwick a;
a.update(0, 1);
a.update(1, 2);
a.update(2, 3);
a.update(3, 4);
a.update(4, 5);
int j = a.sum(0,2);
cout<<j;}

Кроме того, я сделал это правильно? Я имею в виду, я полностью понял идею дерева Фенвика, я просто не могу выяснить, что мы должны делать с исходным массивом? Может быть, мне нужно передать в качестве аргумента класс Фенвика и затем работать с ним? Или просто много обновлений? Заранее спасибо.

0

Решение

Насколько я вижу, вы не инициализировали fentr вектор. Это не будет сбой при обновлении, так как вы переходите на fentr.size(), но при вызове sum,

0

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

Других решений пока нет …

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