无法弄清楚我的二叉索引树解决方案出了什么问题

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]中的所有和作为sum[i]

2.将sum向量排序为克隆向量，并根据其在克隆向量中的索引重新索引sum中的元素。将和元素值作为映射反射的键，将新索引作为反射的值。将向量和元素从后向前添加到二进制索引树中，同时在clone中找到满足上下限条件的有效元素索引范围[idx1，idx2]。

3.在我们的BIT中得到从节点0到节点idx1的和和从节点0至节点idx2的和。如果节点已经插入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]-22.输出：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);

而不是您当前的CCD_ 1。

此外，如果你想多次使用该方法，你需要清除树，将所有值设置回零，而不仅仅是调整它的大小

修复第一个问题使它对您的样本数据有效。我没有注意到您的代码有任何其他问题，但我没有进行彻底的测试。