【英雄哥七月集训】第 25天： 树状数组

---

一、327. 区间和的个数

327. 区间和的个数

给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数 。
区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。
示例 1：
输入：nums = [-2,5,-1], lower = -2, upper = 2
输出：3
解释：存在三个区间：[0,0]、[2,2] 和 [0,2] ，对应的区间和分别是：-2 、-1 、2 。

leetcode327 java

思路

1 前缀和

2 处理边界

3 离散化

4 遍历前缀和

class Solution {
    
    public class BIT{
    
        int n;
        int[] tree;
        public BIT(int x){
    
            this.n = x;
            this.tree = new int[x+1];
        }

        public int lowBit(int x){
    
            return x&(-x);
        }

        public void update(int x){
    
            while(x<=n){
    
                tree[x]++;
                x+=lowBit(x);
            }
        }

        public int query(int x){
    
            int ret = 0;
            while(x!=0){
    
                ret +=tree[x];
                x-=lowBit(x);
            }
            return ret;
        }
    }
    public int countRangeSum(int[] nums, int lower, int upper) {
    
        long sum = 0;
        int res = 0;
        long[] presum = new long[nums.length+1];
        //前缀和
        for(int i = 0 ; i<nums.length ; i++){
    
            sum  += nums[i];
            presum[i+1] = sum;
        }

        //处理边界
        Set<Long>  allnumbers = new TreeSet<>();
        for(long pre:presum){
    
            allnumbers.add(pre);
            allnumbers.add(pre-lower);
            allnumbers.add(pre-upper);
        }

        //离散化
        Map<Long,Integer> map = new HashMap<>();
        int idx = 0;
        for(long x:allnumbers){
    
            map.put(x,idx);
            idx++;
        }

        //遍历前缀和
        BIT bit = new BIT(map.size());
        for(int i =0;i<presum.length;i++){
    
            int left = map.get(presum[i]-upper), right = map.get(presum[i]-lower);
            res +=bit.query(right+1)-bit.query(left);
            bit.update( map.get(presum[i])+1);
        }
        return res;

    }
}

---

总结