Leetcode "Count Range Sum" 尝试求解和优化方案

Question

我正在研究 leetcode 代码挑战，挑战你对合并排序、二分搜索和前缀和的理解

挑战看起来像这样

给定一个整数数组 nums 和两个整数 lower 和 upper，返回包含 [lower, upper] 的范围和的数量。 范围和 S(i, j) 定义为索引 i 和 j 之间的 nums 中元素的总和，其中 i <= j.

我的想法是这样的： 我定义了 sum (i...j) = prefixSum[j] - prefixSum[i-1]，并且我还有一个约束 lo <= sum(i...j) <= hi. Here i can subtitute the sum(i...j) with prefixSum[j] - prefixSum[i-1] giving me lo <= prefixSum[j] - prefixSum[i-1] <= hi. I rearrange the formula to lo - prefixSum[j] <= -prefixSum[i - 1] <= hi - prefixSum[j] and then multiply it with -1 giving me prefixSum[j] - lo >= prefixSum[i - 1] >= prefixSum[j] - hi

设 k = i - 1 => k + 1 = i。所以 i <= j can be replaced to k + 1 <= j and i rearrange the formula to k <= j - 1 which equals to k < j (because it's an integer). so i have 2 formula prefixSum[j] - lo >= prefixSum[k] >= prefixSum[j] - hi 其中 0 <= k < j。这可以在合并排序中完成，因为右子数组中的任何元素总是比左子数组具有更大的索引。而且右子数组中的任何元素都不会遇到左子数组中的元素，因此它满足两个公式。加上子数组已排序，因此可以实现二进制搜索

有关我的想法的更多信息，您可以观看leetcode Count Range Sum by happygirlzt

如果你看过视频，你就会知道她使用的是线性搜索和自上而下的归并排序方法。从我读过的文章（其中一篇是为什么自上而下的合并排序在学习中很受欢迎，而大多数图书馆使用自下而上？）让我意识到自下而上的合并排序的优越性，因为它的缓存位置.我还尝试使用二进制搜索而不是线性搜索，因为 O(log(n)) 优于 O(n)。但是当我尝试提交它时，它给我带来了一个非常独特的问题，即我的算法实际上高估了该值。提交可以在这个链接Count Range sum submission中看到。由此，我认为有些情况我没有涵盖，因为我用二进制搜索和自下而上的合并排序仔细检查了我的实现，而不是我发现的单一问题，检查包括：

1. 算法完成后，我检查我的数组是否已排序
2. 在执行二进制搜索之前，我检查了我当前正在处理的子数组是否已排序
3. 在二进制搜索之后我检查我的 lo 和 hi 是否是正确的意思（lo >= lowerBound 和 hi <= upperBound) Here is my implementation of the binary search

int32_t count(uint32_t i, uint32_t j, int64_t lower_bound, int64_t higherBound ){
        if(i == j){
            int count =  (prefixSum[i] >= lower_bound && prefixSum[i] <= higherBound) ? 1 : 0;
            return count;
        }
        uint32_t lo {i}, hi{j}, mid{};
        int32_t result_lower{}, result_higher{};
        if(prefixSum[j] < lower_bound || prefixSum[i] > higherBound){
            int count = 0;
            return 0;
        } 
        /* Lesser or equal */
        while (j >= i){
            if(i == j){
                result_higher = j;
                break;
            }
            if((j - i + 1) == 2){
                result_higher = (prefixSum[j] <= higherBound) ? j : i; 
                break;
            }
            mid = floor((j + i)/2);
            if(prefixSum[mid] > higherBound){
                j = mid;
                continue;
            }
            i = mid;
        }
        j = hi;
        i = lo;
        /*More or Equal To*/
        while (j >= i)
        {
            if(i == j){
                result_lower = j;
                break;
            }
            if((j - i + 1) == 2){
                result_lower = (prefixSum[i] >= lower_bound) ? i : j; 
                break;
            }
            mid = floor((j + i)/2);
            if(prefixSum[mid] < lower_bound){
                i = mid;
                continue;
            }
            j = mid;
        }
        int count = result_higher - result_lower + 1;
        return result_higher - result_lower + 1;
        
    }

这是我对自底向上归并排序的实现

int countRangeSum(vector<int>& nums, int lower, int upper) {
            prefixSum.resize(nums.size() + 1);
            prefixSum[0] = 0;
            for ( uint32_t i = 1; (i - 1) < nums.size(); i++){
                prefixSum[i] = prefixSum[i-1] + nums[i - 1];
            }
            int64_t counting {};
            for (uint32_t i = 1; i < prefixSum.size(); i <<= 1){
                vector<int64_t> local{};

                for (size_t j = 0; j < prefixSum.size(); j += 2 * i){
                    uint32_t l = j;
                    uint32_t r = j + i;
                    int64_t l_value{}, r_value{};
                    while(l != j + i || (r != j + 2 * i && r < prefixSum.size())){
                        l_value = (l != j + i) ? prefixSum[l] : INT64_MAX;
                        r_value = (r < prefixSum.size() && r != j + 2 * i) ? prefixSum[r] : INT64_MAX;
                        if(r_value < l_value){
                            counting += count(j, j + i - 1, r_value - upper, r_value - lower);
                            local.emplace_back(r_value);
                            r++;
                            continue;
                        }
                        local.emplace_back(l_value);
                        l++;
                    }
                }
                prefixSum = move(local);
            }
            return counting;
        }

我只是不明白比视频提供的更多或更少的实施会失败，因为上面的公式和想法可能存在未发现的案例，我将不胜感激任何形式的帮助。提前谢谢你

PS：为了代码的可读性，我使用“using namespace std”，因为我认为查看一堆 std:: 可能很难阅读