-1

我正在解决一个问题。

    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中的元素。将 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] -2 2 输出：197 预期：3

而且我真的不知道如何格式化我的代码，我总是这样写 c++..

对不起，它有点长，我想了几天仍然不知道哪里出了问题。任何想法表示赞赏！

4

1 回答 1

0

我很难理解您是如何尝试使用二进制索引树的，但我想我明白了。

让我试着解释一下我认为的算法是什么，使用 n 作为输入数组的长度。

  1. 计算范围从索引 0 开始的所有范围和。
  2. 按升序对这些总和进行排序。
  3. 初始化大小为 n 的二叉索引树，表示每个位置的频率计数为 0。这表示您开始的所有总和都是无效的，它将用于跟踪随着算法的进展哪些总和变得有效。
  4. 将所有总和隐式偏移范围总和 S(0, n)，以便获得范围总和，其范围从索引 n 而不是索引 0 开始。
  5. 确定落入 [lower bound, upper bound] 的最小和最大和的排序和列表中的索引。
  6. 查询二叉索引树以计算这些总和中有多少是有效的。将此添加到您对落入 [下限，上限] 的范围和总数的计数中
  7. 确定范围和 S(0,n) 在二叉索引树中的索引，并通过将其频率计数设置为 1 来标记它在下一次迭代中将是一个有效的和。
  8. 循环回到第 4 步，遍历 n - 1, n - 2, n - 3, 。. ., 2, 1, 0。

我认为，您的实现最重要的问题是您的树不够大。它应该大一点，因为没有使用 0 索引。所以使用

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

而不是您当前的+1.

此外，如果您希望能够多次使用该方法，则需要清除树，将所有值设置回零，而不仅仅是调整它的大小。

解决第一个问题使其适用于您的示例数据。我没有注意到您的代码有任何其他问题，但我没有彻底测试。

于 2016-07-21T03:41:17.457 回答