248.Count of Smaller Number-插入区间（中等题）

本文主要是介绍248.Count of Smaller Number-插入区间（中等题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

统计比给定整数小的数的个数

题目

给定一个整数数组（下标由 0 到 n-1，其中 n 表示数组的规模，数值范围由 0 到 10000），以及一个查询列表。对于每一个查询，将会给你一个整数，请你返回该数组中小于给定整数的元素的数量。

注意事项
在做此题前，最好先完成线段树的构造 and 线段树查询 II 这两道题目。
样例

对于数组 [1,2,7,8,5] ，查询 [1,8,5]，返回 [0,4,2]
挑战

可否用一下三种方法完成以上题目。
1.仅用循环方法
2.分类搜索和二进制搜索
3.构建线段树和搜索
题解

public class Solution {class SegmentTreeNode {public int start, end;public int count;public SegmentTreeNode left, right;public SegmentTreeNode(int start, int end, int count) {this.start = start;this.end = end;this.count = count;this.left = this.right = null;}}SegmentTreeNode root;public ArrayList<Integer> countOfSmallerNumber(int[] A, int[] queries) {root = build(0, 10000);ArrayList<Integer> ans = new ArrayList<Integer>();int res;for(int i = 0; i < A.length; i++) {modifySegmentTree(root, A[i], 1);}for(int i = 0; i < queries.length; i++) {res = queries[i] > 0 ? querySegmentTree(root, 0, queries[i] - 1) : 0;ans.add(res);}return ans;}public SegmentTreeNode build(int start, int end) {SegmentTreeNode root = new SegmentTreeNode(start, end, 0);if (start == end){root.count = 0;return root;}int mid = (start + end) / 2;root.left = build(start, mid);root.right = build(mid+1, end);return root;}public int querySegmentTree(SegmentTreeNode root, int start, int end) {if(start == root.start && root.end == end) { return root.count;}int mid = (root.start + root.end)/2;int leftcount = 0;int rightcount = 0;if(start <= mid) {leftcount =  querySegmentTree(root.left, start, Math.min(mid,end));}if(mid < end) {rightcount = querySegmentTree(root.right, start <= mid ? mid+1 : start, end);}  return leftcount + rightcount;}public void modifySegmentTree(SegmentTreeNode root, int index, int value) {if(root.start == index && root.end == index) { root.count += value;return;}int mid = (root.start + root.end) / 2;if(root.start <= index && index <=mid) {modifySegmentTree(root.left, index, value);}if(mid < index && index <= root.end) {modifySegmentTree(root.right, index, value);}root.count = root.left.count + root.right.count;}
}