特殊数据结构-前缀和

本文主要是介绍特殊数据结构-前缀和，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

定义： 针对数组A[1,n],，前k个数组元素之和就是前缀和的概念。
下面给出样例题：
题目： 327. 区间和的个数
网址： https://leetcode-cn.com/problems/count-of-range-sum/

代码

class Solution {
public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        int n = nums.size();
        if(n==0 ||(lower>upper)) return 0;
        vector<long> data;
        long sum=0;
        data.push_back(sum);
        for(auto& digit: nums){
            sum += digit;
            data.push_back(sum);
        }
        return countRangeSort(data, lower, upper, 0, n);
        
    }

    int countRangeSort(vector<long>& data, int lower, int upper, int left, int right){
        if(left==right)
            return 0;
        else{
            int mid = (left + right)/2;
            int n1 = countRangeSort(data, lower, upper, left, mid);
            int n2 = countRangeSort(data, lower, upper, mid+1, right);
            int ret = n1 + n2;

            //计算当前状态的所有符合的和
            int l = mid+1;
            int r = mid+1;
            int i = left;
            while(i<=mid){   //至于为什么能够用归并，其实是利用了前缀数长的序列一定是在右边，所以一定再排序前面先进行统计，否则就出问题。
                while(l<=right && data[l] - data[i] < lower) l++;
                while(r<=right && data[r] - data[i] <= upper ) r++;
                ret += (r-l);
                i++;
            }

            //排序
            vector<long> tmp(right-left+1);   //这个地方实现方法多种，可以考虑是移位实现不使用额外空间
            i=left;
            int j = mid+1;
            int k = 0;
            while(i<=mid && j<=right){
                if(data[i]<=data[j])
                    tmp[k++] = data[i++];
                else
                    tmp[k++] = data[j++];
            }
            while(i<=mid)
                tmp[k++]=data[i++];
            while(j<=right)
                tmp[k++]=data[j++];
            for(i=0;i<=right-left;i++){
                data[i+left]=tmp[i];
            }
            return ret;
        }
    }
};

这个代码是排序-区间和中归并算法的代码，其中的核心一共两个，一个就是前缀和的概念，另一个就是归并排序。

这篇关于特殊数据结构-前缀和的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！