顿搜
飞过闲红千叶，夕岸在哪
类目归类
[Template] Binary Index Tree
10/26
import java.util.Scanner;
public class BinaryIndexedTreeTemplate {
private static int[] tree;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
if (n <= 0) {
return;
}
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = in.nextInt();
}
buildTree(nums);
}
private static void buildTree(int nums[]) {
if (nums == null || nums.length == 0) {
return;
}
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
min = Math.min(min, nums[i]);
max = Math.max(max, nums[i]);
}
tree = new int[max - min + 2]; // Start from 1
for (int i = 0; i < nums.length; i++) {
int val = nums[i] - min + 1;
update(val);
}
}
private static int sum(int x) {
int result = 0;
while (x > 0) {
result += tree[x];
x -= lowBit(x);
}
return result;
}
private static void update(int x) {
while (x < tree.length) {
tree[x]++;
x += lowBit(x);
}
}
private static int lowBit(int x) {
return x & (-x);
}
}
