K
Привет всем, а как найти в дереве Фенвика минимальный индекс, в котором префикс сумма равна заданному значению за O(logN)??
int l = 0, r = n;
while(l < r) {
int midd = l + (r-l)/2;
if (get_sum(BIT, midd+1) < given_sum)
l = midd+1;
else
r = midd;
}
// res => midd + 1
Сейчас нахожу за O(log^2(N)), но наибольший и любой из индексов можно найти за O(logN), поэтому предполагаю, что и наименьший можно.
Обычное дерево Фенвика на массиве BIT(n+1, 0);
void update(vector<int> &BIT, int idx, int delta){
for(int i = idx; i < BIT.size(); i +=(i&-i))
BIT[i] += delta;
}
int get_sum(vector<int>& BIT, int idx){
int sum = 0;
for(int i = idx; i > 0; i-=(i&-i))
sum += BIT[i];
return sum;
}
int l = 0, r = n;
while(l < r) {
int midd = l + (r-l)/2;
if (get_sum(BIT, midd+1) < given_sum)
l = midd+1;
else
r = midd;
}
// res => midd + 1
Сейчас нахожу за O(log^2(N)), но наибольший и любой из индексов можно найти за O(logN), поэтому предполагаю, что и наименьший можно.
Обычное дерево Фенвика на массиве BIT(n+1, 0);
void update(vector<int> &BIT, int idx, int delta){
for(int i = idx; i < BIT.size(); i +=(i&-i))
BIT[i] += delta;
}
int get_sum(vector<int>& BIT, int idx){
int sum = 0;
for(int i = idx; i > 0; i-=(i&-i))
sum += BIT[i];
return sum;
}
а зачем не дерево отрезков?
