树状数组 - wenzhoullq/leetcode GitHub Wiki

树状数组

适用于单点修改,区间求和的数据结构,并且它支持二分找下标和动态加入的数据结构。

求和从右到左，修改/增加从左到右。C[]数组为原数组的len+1,这样就可以统一模板了

  class BIT{
    int[] nums,C;
    int len ;
    public int lowbit(int x){
        return x&(-x);
    }
    public void add(int index,int val){
        int i = index+1;
        while(i<len){
            C[i]+= val;
            i+=lowbit(i);
        }
    }
    public void update(int index,int val){
        int i = index+1, num = val - nums[index];
        nums[index] = val;
        while(i<len){
            C[i]+= num;
            i+=lowbit(i);
        }
    }
    public int query(int index){
        int i = index+1,ans = 0;
        while(i>0){
            ans+=C[i];
            i-=lowbit(i);
        }
        return ans;
    }
    public BIT(int n) {
        len = n+1;
        C = new int[len];
    }

    public int sum(int left, int right) {
        return query(right+1) - query(left);
    }
}

307. 区域和检索 - 数组可修改

离散化

 class BIT{}
 TreeSet<Integer> tm = new TreeSet<>();
 for(int num:nums) {//加入所有的可能的数字
   ts.add(num);
   ts.add();
}
 HashMap<Integer,Integer> m = new HashMap<>();
  int rank = 1;
 for(int key:ts) m.put(,rank++)
 BIT bit = new BIT(rank+10);
 for(int i = 0 ; i < len ; i++){
  int num = m.get();
  int right = , left = ;
  
}

题目

327. 区间和的个数 求前缀,记得加前缀=0的部分和query时候index+1

493. 翻转对

剑指 Offer 51. 数组中的逆序对

775. 全局倒置与局部倒置有快的做法

6198. 满足不等式的数对数目

⚠️ **GitHub.com Fallback** ⚠️