关于数据结构,给定多个整型区间,查询某一个数在不在区间内,返回符合的个数用java语言使用线段树解决问题
时间: 2024-02-27 08:59:21 浏览: 59
信息学数据结构之线段树
好的,针对您的问题,我先简单介绍一下线段树的概念和应用。
线段树是一种二叉树结构,它常用于解决区间查询问题。对于一个区间 [l, r],可以将其拆分为两个子区间 [l, mid] 和 [mid+1, r],然后递归地构建出一棵二叉树。每个节点对应一个区间,叶子节点对应单个元素,而每个非叶子节点对应的区间是其子节点所对应的区间的并集。
线段树的主要优点是可以较快地查询区间内的最大值、最小值、和、乘积等信息,时间复杂度为 O(log n)。
接下来,我为您提供使用线段树解决区间查询问题的Java代码示例:
```java
class SegmentTreeNode {
int start, end;
SegmentTreeNode left, right;
int count;
public SegmentTreeNode(int start, int end) {
this.start = start;
this.end = end;
this.count = 0;
}
}
class SegmentTree {
private SegmentTreeNode root;
public SegmentTree(int[] nums) {
root = buildTree(nums, 0, nums.length - 1);
}
private SegmentTreeNode buildTree(int[] nums, int start, int end) {
if (start > end) {
return null;
} else {
SegmentTreeNode node = new SegmentTreeNode(start, end);
if (start == end) {
node.count = 1;
} else {
int mid = start + (end - start) / 2;
node.left = buildTree(nums, start, mid);
node.right = buildTree(nums, mid + 1, end);
node.count = node.left.count + node.right.count;
}
return node;
}
}
public int query(int start, int end) {
return query(root, start, end);
}
private int query(SegmentTreeNode node, int start, int end) {
if (node == null) {
return 0;
}
if (node.start > end || node.end < start) {
return 0;
}
if (node.start >= start && node.end <= end) {
return node.count;
}
return query(node.left, start, end) + query(node.right, start, end);
}
}
public class Main {
public static void main(String[] args) {
int[] nums = {1, 3, 2, 7, 9, 11};
SegmentTree st = new SegmentTree(nums);
System.out.println(st.query(0, 2)); // 输出 2
System.out.println(st.query(2, 5)); // 输出 4
}
}
```
在这个示例中,我们首先定义了 `SegmentTreeNode` 类和 `SegmentTree` 类。`SegmentTreeNode` 表示线段树的节点,其中 `start` 和 `end` 分别表示节点对应的区间的左右端点,`left` 和 `right` 分别表示节点的左右子节点,`count` 表示节点对应区间内的数的个数。`SegmentTree` 表示线段树的类,其中 `root` 表示线段树的根节点。
在构建线段树时,我们首先判断当前区间是否为空,若为空则返回 null。否则,若当前区间只有一个元素,则将其 count 设置为 1;否则,将当前区间拆分为两个子区间,并递归地构建左右子树,最后将当前节点的 count 设置为其左右子树的 count 之和。
在查询时,我们首先判断当前节点是否为空,若为空则返回 0。然后判断当前节点所对应的区间与查询区间的关系,若两个区间没有交集,则返回 0;若当前节点所对应的区间完全包含于查询区间内,则返回当前节点的 count;否则,递归地查询左右子树,并将结果相加。
以上就是使用线段树解决区间查询问题的Java代码示例,希望能够对您有所帮助!
阅读全文