树状数组

模板

本文使用notionai生成大纲+oi wiki内容组合生成

例题

这里记录一些标了线段树标签的树状数组题，因为实现简单，复杂度和线段树相似，所以基本上可以使用树状数组实现的题目基本上都不会主动选用线段树。不过也不太会主动用那个技巧去强行做线段树的事，因为实现一样麻烦。

逆序对1

这题比较特殊的地方是题干其实很简单就是一个不等式转换一下以后求逆序对。但是比较有意思的是，逆序对除了用归并以外还可以用树状数组求解。但是使用树状数组求解逆序对的话有一个比较麻烦的地方，就是这些逆序对的值域如果过大，需要提前把这些逆序对离散化，然后通过二分查找来确定要插入和查询下标。离散的方法是统计这些数，然后去重，排序。使用二分查找某个数的下标，然后根据排序后的下标对树状数组进行操作。这一步排序的目的是为了在插入时，保持原数组的大小关系。

逆序对2

这题和上面的题基本上一样，可以离散化也可以加一个offset直接构建树状数组，需要注意的事如果进行离散化的时候查找下标时要+1，否则下标会从0开始。

离散化code

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        int [] k ;
        k = Arrays.stream(nums).distinct().sorted().toArray();
//        for(int i = 0 ; i< k .length ; i++)System.out.print(k[i]+" ");
//        System.out.println();
        Bit bit = new Bit(nums.length+1);
        List<Integer> ans = new ArrayList<>();
        for(int i = nums.length-1 ; i >=0 ; i --){
            int p = lowerbound(k,nums[i])+1;
//            System.out.println(p+" "+nums[i]);
            ans.add(bit.query(p-1));
            bit.add(p);
        }
        Collections.reverse(ans);
        return ans;
    }
    int lowerbound(int []b , int target){
        int left =0 ,right = b.length-1;
        while(left<=right){
            int mid = left+(right-left)/2;
            if(b[mid]<target){
                left = mid+1;
            }else {
                right = mid-1;
            }
        }
        return left;
    }
    class Bit{
        int [] b;
        public Bit(int n ){
            b = new int[n];
        }
    int lowbit(int x){
            return x&(-x);
        }
    int query(int x){
            int ans = 0;
            for(int i = x ; i>0 ; i-=lowbit(i) ){
                ans+=b[i];
            }return ans;
        }
    void add(int x){

            for(int i = x ; i < b.length ;i+=lowbit(i)){
                b[i]++;
            }
        }

    }

}

offset code

class Solution {
    public List<Integer> countSmaller(int[] nums) {

        Bit bit = new Bit(20000+10);
        List<Integer> ans = new ArrayList<>();
        for(int i = nums.length-1 ; i >=0 ; i --){
            int k =bit.query(nums[i]-1);
            ans.add(k);
            bit.add(nums[i]);
        }
        Collections.reverse(ans);

        return ans;
    }
    class Bit{
        int Base = 10010;
        int [] b;
        public Bit(int n ){
            b = new int[n];
        }
    int lowbit(int x){
            
            return x&(-x);
        }
    int query(int x){
            int ans = 0;
            x+=Base;
            for(int i = x ; i>0 ; i-=lowbit(i) ){
                ans+=b[i];
            }return ans;
        }
        void add(int x){
            x+=Base;
            for(int i = x ; i < b.length ;i+=lowbit(i)){
                b[i]++;
            }
        }

    }

}

什么是树状数组

树状数组是一种数据结构，用于解决一类数组问题，如单点修改、区间求和等。它可以在 O(log n) 的时间复杂度内完成这些操作，比暴力算法更快。

树状数组的原理

树状数组的原理是将一个数组分解成若干个子数组，每个子数组的长度是 2 的幂次方，然后用这些子数组去存储原数组中的元素。在修改或查询时，通过修改或查询对应的子数组，来实现对原数组的修改或查询。

树状数组的实现

树状数组的实现主要包括两个操作：单点修改和区间查询。单点修改是指将某个位置的元素修改为新的值，区间查询是指查询某个区间内所有元素的和。

创建与维护

由于树状数组的某些性质，让每个节点维护的区间为[r-lowbit(r)+1,r]，且每个节点的直接父节点是x+lowbit(x),所以我们只需要在更新i的时候同步其直接父节点即可On建树。

void init(){
		for(int i = 1 ; i <= n ; i ++){
				int fa = i+lowbit(i);
				c[i]+=nums[i];
				if(fa<=n){
						c[fa]+=c[i];
				}
		}
}

单点修改

单点修改的实现步骤如下：

找到要修改的位置对应的子数组。

修改该子数组中对应的元素。

重新计算该子数组及其父节点的前缀和。

void add(int x, int k) {
  while(x<=n){
		c[x]+=k;
		x+=lowbit(x);
	}
}

区间查询

区间查询的实现步骤如下：

找到要查询的区间对应的子数组。

计算该子数组中对应元素的值，加入到查询结果中。

通过修改子数组的左右边界，递归查询左右子数组。

int getsum(int x) {  // a[1]..a[x]的和
  int ans = 0;
	while(x!=0){
		ans+=c[x];
		x-=lowbit(x);
	}
	return ans;
}

树状数组的应用

树状数组主要用于解决一类数组问题，如单点修改、区间求和等。它在许多算法竞赛和实际应用中都有广泛的应用，如求逆序对、求排名、求区间众数等。

树状数组还有一个比较有意思的trick

通过维护差分数组实现区间查询区间更新的效果。原理是这样的，由于差分数组只能区间更新，单点查询。且差分数组的原理是d[n] = nums[n]-nums[n-1];而sum(a,n)就等于懒得写latex了，具体推导看oiwiki吧。总之只需要维护一个di的前缀和以及一个di*i的前缀和就可以通过这两个前缀和实现sum(a,i)的效果也就是说差分一下就可以直接实现区间查询的能力了。而更新的时候只需要对两个树状数组的di加上k/k*i以及对dj+1减去k/k*j+1即可。通过这个技巧可以比较简单的实现裸线段树的功能吧（雾）。