首页 > 其他分享 >树状数组

树状数组

时间:2024-04-22 13:11:06浏览次数:25  
标签:树状 int lowbit static 数组 query

1.0 树状数组概念 

【五分钟丝滑动画讲解 | 树状数组 | 21智人马同学】 

  • 树状数组用于高效计算数组前缀和及支持单点更新操作。与前缀和区别在于树状数组可以在O(log n) 的时间复杂度支持单点更新操作。

其数学证明 参考 树状数组的基本原理

 

1.1 树状数组的性质

  • lowbit函数 : lowbit(i) = i & -i
    lowbit(int x)"函数是用来获取一个整数 x 的最低位的 1 所代表的值,也就是 x 的二进制表示中最右边的 1 所在的位置上的数值。                                                                 (例如:10  = 1010,lowbit(10) = 2),这个函数常用于树状数组等数据结构中,用于快速定位需要操作的位置或计算位信息。
  • 求和性质:序号为i的序列正好就是长度为lowBit(i)且以i结尾的序列.如下图来自  21智人马同学 
     

 

// 树状数组递归求前缀和函数
public long count(int p) {
    if (p == 0) {
        return 0;
    }
    return count(p - lowbit(p)) + b[p];
}

 

  • 修改某个值性质:一个序列b[i]正上方的序列,正好就是b[i + lowBit(i)]

   因为树状数组每个点维护的是其自身及其前面 lowbit(x) 个位置的区间和,当需要修改某个值时,我们需要更新当前位置及其受影响的后续位置,具体步骤为:

    1.   首先,修改当前位置p的值。

    2.   然后,从当前位置 p 开始,沿着树状数组的结构向后更新。对于树状数组中的每个受影响位置,我们需要将其值增加 x

    3.   更新完当前位置后,将 p 更新为下一个需要更新的位置,即加上 lowbit(p),继续进行更新,直到超出数组范围为止。

 

// 树状数组的单点更新函数
public void add(int p, int x) {
    while (p < N) {
        b[p] += x;
        p += lowbit(p);
    }
}

 

1.2 BinaryIndexedTree 数据结构

 

package com.coedes.binaryindextree;

/**
 * @description:树状数组
 * @author: wenLiu
 * @create: 2024/4/22 11:00
 */
public class BinaryIndexedTree {
    private int[] BITree;
    private int[] nums; // 原始数组

    public BinaryIndexedTree(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        this.BITree = new int[n + 1]; // 树状数组使用 1-based 索引

        // 初始化树状数组
        for (int i = 0; i < n; i++) {
            update(i, nums[i]); // 利用 update 函数构建初始树状数组
        }
    }

    // 单点更新:将索引 i 处的元素增加 delta
    public void update(int i, int delta) {
        i++; // 转换为树状数组的索引,从 1 开始

        while (i < BITree.length) {
            BITree[i] += delta;
            i += lowbit(i); // 更新下一个节点
        }
    }

    // 查询前缀和:查询索引 0 到 i 的元素和
    public int query(int i) {
        i++; // 转换为树状数组的索引,从 1 开始

        int sum = 0;
        while (i > 0) {
            sum += BITree[i];
            i -= lowbit(i); // 向前查询前缀和
        }

        return sum;
    }

    // 查询区间 [left, right] 的元素和
    public int rangeSum(int left, int right) {
        if (left > 0) {
            return query(right) - query(left - 1);
        } else {
            return query(right); // left = 0 的情况
        }
    }

    // 计算 x 的最低位 1 所代表的值,即 lowbit(x)
    private int lowbit(int x) {
        return x & (-x);
    }
}

 

1.3 树形数组应用

1.3.1 动态前缀和

题目描述: 给定一个长度为 n 的初始值为 0 的数组,共进行 m 次操作。每次操作作为一行输入,操作类型由第一个数 op 决定:

  1. op = 1,后面接两个整数 xd1 ≤ x ≤ n1 ≤ d ≤ 10^5),表示将数组位置 x 的值增加 d
  2. op = 2,后面接两个整数 lr1 ≤ l ≤ r ≤ n),表示查询数组区间 [l, r] 的总和,并输出一个正整数作为结果。

输入描述:

  • 第一行输入两个整数 nm1 ≤ n, m ≤ 100,000)。
  • 接下来 m 行,每行输入三个正整数,表示操作类型和对应的参数。

输出描述:

  • 对于每次查询操作,输出一个正整数表示当前区间的和。
input:
4 4
1 2 3
2 1 3
1 3 4
2 2 3

out:

3
7

 

package com.coedes.binary_index_tree.dynamic_prefix_sum;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


/**
 * @description:动态前缀和
 * @author: wenLiu
 * @create: 2024/4/22 12:06
 */
public class Main {
    static final int N = 100010;
    static int[] biTree = new int[N];

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] s = reader.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        for (int i = 0; i < m; i++) {
            String[] s1 = reader.readLine().split(" ");
            int op = Integer.parseInt(s1[0]);
            int val1 = Integer.parseInt(s1[1]);
            int val2 = Integer.parseInt(s1[2]);
            if (op == 1) {
                add(val1, val2);
            } else {
                System.out.println(query(val2) - query(val1 - 1));
            }
        }
    }


    private static long query(int p) {
        long sum = 0;
        while (p > 0) {
            sum += biTree[p];
            p -= lowbit(p);
        }
        return sum;
    }

    private static void add(int p, int val) {
        while (p <= N) {
            biTree[p] += val;
            p += lowbit(p);
        }
    }

    private static int lowbit(int p) {
        return p & (-p);
    }
}

1.3.2 求逆序对数量

逆序对是指数组中所有满足 i < j 且 ai > aj的位置对(i, j),要求计算长度为n的数组中的逆序对总数。

朴素法

    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(a[i]>a[j]){
                cnt++;
            }
        }
    }

 

树形数组法:

add(x,1)的意义就是当前数值为的数字出现次数+1,

从右往左统计,即统计比当前位置  i  的 ai 小的值的元素个数

例如求[3 2 1 4]逆序对个数:

query:3(4-1)
bt :0 0 0 1
query:0
bt :1 1 0 2
query:1
bt :1 2 0 3
query:2
bt :1 2 1 4

package com.coedes.binary_index_tree.reverse_order;

/**
 * @description:TODO
 * @author: wenLiu
 * @create: 2024/4/22 12:42
 */
import javax.sound.midi.Soundbank;
import java.util.Scanner;

public class Main {
    static final int N = (int)1E5 + 10;
    static int[] tr = new int[N];
    static int n;
    static int[] a = new int[N];

    static int lowbit(int x) {    // 计算最后一位1的位置
        return x & -x;
    }

    static void add(int x, int d) {   // 在第x位置上+d
        for (int i = x; i <= n; i += lowbit(i)) {
            tr[i] += d;
        }
    }

    static long query(int x) {  // 求1~x的和(前缀和)
        long ans = 0; // 开long long,省的爆int
        for (int i = x; i > 0; i -= lowbit(i)) {
            ans += tr[i];
        }
        return ans;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        long cnt = 0;  // 逆序对个数
        for (int i = n - 1; i >= 0; i--) {
            System.out.println("query:" + (a[i] - 1));
            int num = (int)query(a[i] - 1);  // 查询比a[i]小的元素数量
            cnt += num;
            add(a[i], 1);  // 将当前元素添加到树状数组中
            for (int i1 = 0; i1 < n + 1; i1++) {
                System.out.print(tr[i1]+" ");
            }
            System.out.println();
        }
        System.out.println(cnt);
    }
}

  

 

 

 

 

 

标签:树状,int,lowbit,static,数组,query
From: https://www.cnblogs.com/alohablogs/p/18150083

相关文章

  • 6.Java数组
    Java数组数组概述相同类型数据的有序集合通过下标访问他们数组的声明与创建publicclassArrayDemo01{publicstaticvoidmain(String[]args){//变量类型变量名字=变量的值int[]nums;//1.声明一个数组首选//intnums2[]......
  • 34天【代码随想录算法训练营34期】第八章 贪心算法 part03 (● 1005.K次取反后最大化
    1005.K次取反后最大化的数组和classSolution:deflargestSumAfterKNegations(self,nums:List[int],k:int)->int:nums.sort(key=lambdax:abs(x),reverse=True)foriinrange(len(nums)):ifnums[i]<0andk>0:......
  • JavaScript 数组增强
    Javascript的数组最近通过新的原型方法(例如toReversed、toSorted、toSpliced和with)获得了新的力量。这些新方法提供了在JavaScript中更改数组的额外方​​法。它允许进行更改并获取包含这些更改的数组的新副本。 Array.prototype.toReversed:-此方法返回一个新数组,其元素顺......
  • js数组转成树形结构
    js将数组转成对应的树形结构:functiontransformArrayToObject(array){ constresult={}; array.forEach(item=>{ const{ id, name, pid, flag }=item; if(pid==0){ result[name]={ id, flag, pid } }else{ transfo......
  • 【js】两个数组对象合并成一个树结构的数据
    1模板2/**3*合并两个数组,将岗位信息按照部门进行分组4*@param{Array}array1岗位信息数组,每个岗位包含部门ID(deptId)、岗位ID(postId)和岗位名称(postName)5*@param{Array}array2部门信息数组,每个部门包含部门ID(id)和部门名称(label)6*@returns{Arr......
  • 树状数组入门
    树状数组下标记得是从1开始,本节点id通过加lowbit可以访问到父节点的id,用于点修。本节点id减去lowbit则是查看左边第一个比自己高一级的节点id,比如7会查到6,6会查到4,这样子累加此三个的值就可以得到前七个的前缀和。inttreeArr[M]={0};//startfrom1intlowbit(intx){......
  • 在React中的函数组件和类组件——附带示例的对比
    在React中,创建组件有两种主要方式:函数组件和类组件。每种方式都有自己的语法和用例,尽管随着ReactHooks的引入,它们之间的差距已经显著缩小。但选择适当的组件类型对于构建高效和可维护的React应用程序仍然非常关键。在本文中,我们将探讨函数和类组件之间的基本区别,清楚地理解它们......
  • 发转数组的操作
    publicclassDemo4{publicstaticvoidmain(String[]args){int[]arrays={1,2,3,4,5};//printArrary(arrays);//JDK1.5,没有下标//for(intarray:arrays){//System.out.println(array);//array代表数组的数值int[]reverse=reverse(arrays);printArrary(re......
  • 数组的使用
    publicclassDmo03{publicstaticvoidmain(String[]args){int[]arrays={1,2,3,4,5};//打印全部的数组元素for(inti=0;i<arrays.length;i++){System.out.println(arrays[i]);}System.out.println("====");//计算所有元素的和intsum=0;for(inti=0;i<arr......
  • 数组题目
    数组问题1密码验证:程序设定的密码是“Y1N2ab”,从键盘输入密码(密码长度不超过10),和设定密码相比较,密码正确的话输出“that'sok”,程序结束;错误的话提示再次输入密码,最多允许输3次数组问题二编程将一个16进制的字符串转化为十进制数,如“2A”转化为42。字符串应该仅的数字和大......