区间和的个数 线段树查询修改 离散化

const int N = 40005;

class SegmentTree {
   
public:
    struct {
   
        int val;
        int l, r;
    }tree[N];
    
    inline int ls(int root)
    {
   
        return root << 1;
    }

    inline int rs(int root)
    {
   
        return (root << 1) + 1;
    }

    void build(int root, int left, int right)
    {
   
        tree[root].l = left;
        tree[root].r = right;
        tree[root].val = 0;

        if (left == right) {
   
            return;
        }

        int mid = (left + right) >> 1;
        build(ls(root), left, mid);
        build(rs(root), mid + 1, right);
    }

    int query(int root, int left, int right)
    {
   
        if (tree[root].l == left and tree[root].r == right) {
   
            return tree[root].val;
        }

        int mid = (tree[root].l + tree[root].r) >> 1;

        if (right <= mid) {
   
            return query(ls(root), left, right);
        }
        else if (left > mid) {
   
            return query(rs(root), left, right);
        }
        else {
   
            return query(ls(root), left, mid) + query(rs(root), mid + 1, right);
        }
    }

    void insert(int root, int pos)
    {
   
        ++tree[root].val;
        if (tree[root].l == tree[root].r)
            return;
        
        int mid = (tree[root].l + tree[root].r) >> 1;

        if (pos <= mid) {
   
            insert(ls(root), pos);
        }
        else {
   
            insert(rs(root), pos);
        }
    }
};

class Solution {
   
public:
    using ll = long long;

    ll preSum[N];
    vector<ll> vals;
    SegmentTree tree;

    ll find(ll x)
    {
   
        return lower_bound(vals.begin(), vals.end(), x) - vals.begin();
    }

    int countRangeSum(vector<int> nums, int lower, int upper)
    {
      
        int n = (int)nums.size();

        for (int i = 1; i <= n; ++i) {
   
            preSum[i] = preSum[i - 1] + nums[i - 1];    //求前缀和
        }

        for (int i = 0; i <= n; ++i) {
   
            vals.push_back(preSum[i]);
            vals.push_back(preSum[i] - lower);
            vals.push_back(preSum[i] - upper);
        }
        //将前缀和 和 满足lower和upper条件的值离散化。

        sort(vals.begin(), vals.end());
        vals.erase(unique(vals.begin(), vals.end()), vals.end());

        int res = 0;
        tree.build(1, 1, vals.size());

        for (int i = 0; i <= n; ++i) {
   
            ll l_bound = preSum[i] - upper, r_bound = preSum[i] - lower;
            res += tree.query(1, find(l_bound + 1), find(r_bound + 1));
            tree.insert(1, find(preSum[i]) + 1);
        }

        return res;
    }
};