Не могу понять, что не так с моим решением Binary Indexed Tree

Я решаю проблему.

    Count of Range Sum

Given an integer array nums, return the number of range sums that
lie in [lower, upper] inclusive. Range sum S(i, j) is defined as
the sum of the elements in nums between indices i and j (i ≤ j),inclusive.
Example: Given nums = [-2, 5, -1], lower = -2, upper = 2, Return 3.
The three ranges are : [0, 0], [2, 2], [0, 2] and their respective sums are: -2, -1, 2

Мое решение ниже:

1. получить все суммы из [0, i] как сумму [i]

2.сортируйте вектор суммы как вектор клона, и переиндексируйте элементы в сумме согласно его индексу в векторе клона. Поместите значение элемента суммы как ключ отражения карты, новый индекс как значение отражения. добавьте элемент вектора суммы от начала до конца в двоичное индексированное дерево и в то же время найдите допустимый диапазон индекса элементов [idx1, idx2] в клоне, который удовлетворяет условию нижней и верхней границ.

3. получить сумму от узла 0 до узла idx1 и сумму от узла 0 до узла idx2 в нашем BIT. Если узел уже вставлен в BIT, мы найдем узел в нашем BIT. Таким образом, количество узлов, которое удовлетворяет нашему ограниченному условию, является суммой.

 public:
vector<long>tree,clone;
int countRangeSum(vector<int>& nums, int lower, int upper) {
int n=nums.size();
vector<long>sum(n+1);
for(int i=1;i<=n;i++)
sum[i]=sum[i-1]+nums[i-1];// step1

clone=sum;
sort(clone.begin(),clone.end());
tree.resize(sum.size()+1);
unordered_map<long,int>reflect;
for(int i=0;i<clone.size();i++)
reflect[clone[i]]=i;//step2

int res=0;
for(int i=sum.size()-1;i>=0;i--)
{

int idx1=binarysearch(sum[i]+lower,true);
int idx2=binarysearch(sum[i]+upper,false);

res=res+count(idx2)-count(idx1);
add(reflect[sum[i]]); //step3
}
return res;
}int binarysearch(long val, bool includeself)
{
if(includeself)
return lower_bound(clone.begin(),clone.end(),val)-clone.begin();
return upper_bound(clone.begin(),clone.end(),val)-clone.begin();
}
void add(int pos){
pos=pos+1;
while(pos<tree.size())
{
tree[pos]++;
pos=pos+(pos&-pos);
}
}int count(int pos){
int cnt=0;
pos=pos+1;
while(pos>0)
{
cnt=cnt+tree[pos];
pos=pos-(pos&-pos);
}
return cnt;
}

Ошибки:
Входные данные:
[-2,5, -1] -2
2
Выход:
197
Ожидаемое:
3

И я действительно не знаю, как отформатировать мой код, я всегда писал C ++, как это так …

Извините, это становится немного длинным, я думал, что это в течение нескольких дней все еще понятия не имею, где идет не так, как надо. Любая мысль ценится !!

-1

Решение

Мне было трудно понять, как вы пытаетесь использовать двоичное индексированное дерево, но я думаю, что оно у меня есть.

Позвольте мне попытаться объяснить, что я думаю, алгоритм, используя n в качестве длины входного массива.

  1. Вычислить все суммы диапазона, для которых диапазон начинается с индекса 0.
  2. Сортируйте эти суммы в порядке возрастания.
  3. Инициализируйте двоичное индексированное дерево размера n, которое представляет счетчик частоты 0 в каждой позиции. Это означает, что все суммы, с которых вы начинаете, являются недействительными, и будут использоваться для отслеживания того, какие суммы становятся действительными по мере выполнения алгоритма.
  4. Неявно смещайте все суммы на сумму S (0, n) диапазона, чтобы получить суммы диапазона, для которых диапазон начинается с индекса n, а не с индекса 0.
  5. Определите индексы в списке отсортированных сумм наименьшей и наибольшей суммы, попадающей в [нижняя граница, верхняя граница].
  6. Запросите двоичное индексированное дерево, чтобы подсчитать, сколько из этих сумм является действительными. Добавьте это к вашему количеству общего количества сумм диапазона, попадающих в [нижняя граница, верхняя граница]
  7. Определите индекс суммы диапазона S (0, n) в двоичном индексированном дереве и отметьте, что он будет действительной суммой в следующей итерации, установив его счетчик частоты равным 1.
  8. Вернемся к шагу 4, повторяя n — 1, n — 2, n — 3,. , ., 2, 1, 0.

Я думаю, что наиболее существенная проблема с вашей реализацией заключается в том, что ваше дерево недостаточно велико. Это должно быть немного больше, потому что индекс 0 не используется. Так что используйте

tree.resize(sum.size()+2);

вместо вашего текущего +1,

Также, если вы хотите использовать метод более одного раза, вам нужно очистить дерево, вернув все значения к нулю, а не просто изменив его размер.

Исправление первой проблемы заставило его работать с вашими примерами данных. Я не заметил каких-либо других проблем с вашим кодом, но я не провел тщательного тестирования.

0

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

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

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