树状数组
说明:
核心点: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;
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]); }
System.out.println("输出n个的和:"); int n = sc.nextInt(); System.out.println(countSum(tree,n));
System.out.println("输出start -> end 的和"); int start = sc.nextInt(); int end = sc.nextInt(); System.out.println(countSum(tree,end)-countSum(tree,start-1));
}
public static int lowBit(int i){ return i&(-i); }
public static void update(int tree[],int i,int v){ while(i<tree.length){ tree[i] += v; i += lowBit(i); } }
public static long countSum(int tree[],int i){ long ans = 0; while(i>0){ ans+= tree[i]; i -= lowBit(i); } return ans; }
}
|