树状数组(java)

2024-01-21 04:57| 来源: 网络整理| 查看: 265

树状数组问题模型

树状数组是一个查询和修改复杂度都为log(n)的数据结构。

首先我们搞明白树状数组是用来干嘛的，现在有一个这样的问题：有一个数组a，下标从0到n-1，现在给你w次修改，q次查询，修改的话是修改数组中某一个元素的值；查询的话是查询数组中任意一个区间的和，w + q < 500000。

这个问题很常见，首先分析下朴素做法的时间复杂度，修改是O ( 1 ) O(1)O(1)的时间复杂度，而查询的话是O ( n ) O(n)O(n)的复杂度，总体时间复杂度为O ( q n ) O(qn)O(qn)；可能你会想到前缀和来优化这个查询，我们也来分析下，查询的话是O ( 1 ) O(1)O(1)的复杂度，而修改的时候修改一个点，那么在之后的所有前缀和都要更新，所以修改的时间复杂度是O ( n ) O(n)O(n)，总体时间复杂度还是O ( q n ) O(qn)O(qn)。

可以发现，两种做法中，要么查询是O ( 1 ) O(1)O(1)，修改是O ( n ) O(n)O(n)；要么修改是O ( 1 ) O(1)O(1)，查询是O ( n ) O(n)O(n)。那么就有没有一种做法可以综合一下这两种朴素做法，然后整体时间复杂度可以降一个数量级呢？有的，对，就是树状数组。

模板 lowbit（）函数

这个函数的功能就是求某一个数的二进制表示中最低的一位1所表示的数，比如6（110）返回2（10）

代码

static int lowbit(int x) { return x&(-x); } add（）函数

构造树状数组的前缀和

代码

static void add(int i,int value) { //构造树状数组的前缀和 while(i //求前缀和 int sum=0; while(i>0) { sum+=pre[i]; i-=lowbit(i); } return sum; } 示例 import java.util.Scanner; public class Main { static Scanner scanner=new Scanner(System.in); static int maxlenth=100; static int []c=new int[maxlenth]; static int lowbit(int x) { return x&(-x); } static void add(int i,int value) { while(i int sum=0; while(i>0) { sum+=c[i]; i-=lowbit(i); } return sum; } public static void main(String[] args) { for(int i=1;i

【本文地址】

公司简介

联系我们