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

Question

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

    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++, как это так...

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

Answer 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,

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

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