区间和的个数（multiset/线段树/归并）

原题 给定一个整数数组 nums，返回区间和在 [lower, upper] 之间的个数，包含 lower 和 upper。 区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。 参考

multiset

class Solution {
public:
    int countRangeSum(vector& nums, int lower, int upper) {
        int n = nums.size();
        multiset st;
        st.insert(0);
        long long sum = 0;
        int ans = 0,l,r;
        for(auto val:nums) {
            sum += val;
            ans += distance(st.lower_bound(sum-upper),st.upper_bound(sum-lower));
            st.insert(sum);
        }
        return ans;
    }
};

线段树+离散化

class Solution {
public:
    int countRangeSum(vector& nums, int lower, int upper) {
        int n = nums.size(),pos,a,b;
        int ans = 0;
        vector h(n+1);
        h[0] = 0;
        for(int i = 1;i