顿搜
飞过闲红千叶，夕岸在哪
类目归类
[Template] Segment Tree
10/26
import java.util.Scanner;
class Tree {
int left;
int right;
int count; //Stand for what you want to record
Tree(int l, int r) {
left = l;
right = r;
}
}
public class SegmentTreeTemplate {
private static Tree[] 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();
}
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 Tree[4 * (max - min + 1)];
buildTree(min, max, 1);
}
private static void buildTree(int l, int r, int index) {
if (l > r) {
return;
}
tree[index] = new Tree(l, r);
if (l == r) {
return;
}
int mid = l + ((r - l) >> 1);
buildTree(l, mid, index << 1);
buildTree(mid + 1, r, index << 1 | 1);
}
private static void update(int val, int index) {
if (tree[index].left > val || tree[index].right < val) {
return;
}
tree[index].count ++;
if (tree[index].left == tree[index].right) {
return;
}
int mid = tree[index].left + ((tree[index].right - tree[index].left) >> 1);
if (val <= mid) {
update(val, index << 1);
} else {
update(val, index << 1 | 1);
}
}
private static int sum(int val, int index) {
if (tree[index].right <= val) {
return tree[index].count;
}
if (val < tree[index].left) {
return 0;
}
int mid = tree[index].left + ((tree[index].right - tree[index].left) >> 1);
if (val <= mid) {
return sum(val, index << 1);
} else {
return sum(val, index << 1) + sum(val, index << 1 | 1);
}
}
}
