树状数组

说明：

核心点：lowbit()函数

  • 该函数是用来求二进制数（从右往左数）第一个1以及后面的0组成的值。

    例如：lowbit(10100)=100。（都是二进制数）

    lowbit(x)=x&(-x),x为二进制数。

    （对于一个二进制数x，-x相当于按位取反再加1，即求其补码。&就是将其补码的x按位做与运算。）

讲解视屏：

五分钟丝滑动画讲解 | 树状数组_哔哩哔哩_bilibili

相应文章：

树状数组详解 - Xenny - 博客园 (cnblogs.com)

《算法竞赛》上册 罗勇军 第160页

题目推荐：

敌兵布阵 - HDU 1166 - Virtual Judge (vjudge.net)

Java代码模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

import java.util.Scanner;

/**
 * @description: 树状数组
 * @author 长白崎
 * @date 2023/5/2 1:27
 * @version 1.0
 */
public class BinaryIndexedTrees {

    public static void main(String[] args) {

        //测试条例
        Scanner sc = new Scanner(System.in);

        //数组长度
        System.out.println("输入数组长度：");
        int num = sc.nextInt();
        int data[] = new int[num+1];
        int tree[] = new int[(num+1)*4];
        System.out.println("输入数组每个元素的值");
        for(int i=1 ; i <= num ; ++i){
            data[i] = sc.nextInt();
            update(tree,i,data[i]);
        }

        //输出数组前i个之和
        System.out.println("输出n个的和：");
        int n = sc.nextInt();
        System.out.println(countSum(tree,n));

        //输出start -> end 的和
        System.out.println("输出start -> end 的和");
        int start = sc.nextInt();
        int end = sc.nextInt();
        System.out.println(countSum(tree,end)-countSum(tree,start-1));

    }


    /**
     * lowBit函数,用于通过原data存储数组中对应的下标计算出树状数组中对应的位置下标。
     * @param i
     * @return
     */
    public static int lowBit(int i){
        return i&(-i);
    }

    /**
     * update函数，用于更新树状数组的值
     * @param tree 树状数组
     * @param i 表示更新第i个数组的下标的值
     * @param v 更新的值（即在原值的基础上做加法或其他）
     */
    public static void update(int tree[],int i,int v){
        while(i<tree.length){
            tree[i] += v;
            i += lowBit(i);
        }
    }


    /**
     * countSum，用于计算数组中前i个之和
     * @param tree 树状数组
     * @param i 这表示前i个之和
     * @return 返回和值
     */
    public static long countSum(int tree[],int i){
        long ans = 0;
        while(i>0){
            ans+= tree[i];
            i -= lowBit(i);
        }
        return ans;
    }

}