给定数组，求出数组每个数左边比该数小的数的个数

1.问题描述

​ 给定一个数组num,数组长度为n,求出数组中每个数左边比该数小的数的个数

2.做法

是一道比较典型的线段树的题目．

具体做法是我们以数组中最小的数low和最大的数high为线段树根节点的两个端点，建立线段树，线段树所有节点的权值初始为空.

接着在线段树中依次查询数组中的数x，找到相应的位置．找到后，权值+1，并向上改变父节点的权值，这里是为了统计数组中落在[l,r]区间的数的个数．

最后求解答案时我们只需要在线段树中寻找[low,x-1]节点的值就好，具体过程参考代码（java实现）

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static int a;
    public static int b;
    public static int c;
    final static int INF = 0xffffff;
    final static int LOW = -0xfffffff;
    public static class SegmentTreeNode {
        SegmentTreeNode leftChild;
        SegmentTreeNode rightChild;
        public int count;
        public int left;
        public int right;
        public int cover;
        public SegmentTreeNode(int left, int right) {
            this.left = left;
            this.right = right;
            this.count = 0;
            this.cover = 0;
        }
    }//java线段树的实现

    public static void build(SegmentTreeNode root){//建立线段树
        int left = root.left;
        int right = root.right;
        if(left >= right){
            return;
        }else{
            int mid = (left + right) / 2;
            SegmentTreeNode l = new SegmentTreeNode(left,mid);
            SegmentTreeNode r = new SegmentTreeNode(mid + 1,right);
            root.leftChild = l;
            root.rightChild = r;
            build(l);
            build(r);
        }
    }

    public static void modfy(SegmentTreeNode root,int index){//查找数字的位置
        int left = root.left;
        int right = root.right;
        int mid = (left + right)/2;
        if ( left == right){
            root.count += 1;
            return;
        }
        if(left > right){
            return;
        }
        if(index <= mid){
            modfy(root.leftChild,index);
        }else if(index > mid){
            modfy(root.rightChild,index);
        }
        root.count = root.leftChild.count + root.rightChild.count;
    }

    public static int quarry(SegmentTreeNode root,int start,int end){//进行查询
        if (start > end || root.left > root.right){
            return 0;
        }
        if(start <= root.left && end >= root.right){
            return root.count;
        }
        int mid = (root.left + root.right) / 2;
        if (start > mid){
            return quarry(root.rightChild ,start ,end);
        }else if(end < mid + 1){
            return quarry(root.leftChild ,start ,end);
        }else{
            return (quarry(root.leftChild ,start ,mid) + quarry(root.rightChild,mid+1,end));
        }
    }

    public static void init(){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int min = INF;
        int max = LOW;
        int[] num = new int[n];
        for (int i = 0;i < n;i++){
            num[i] = input.nextInt();
            min = Math.min(min,num[i]);
            max = Math.max(max,num[i]);
        }
        SegmentTreeNode root = new SegmentTreeNode(min,max);
        build(root);
        for (int i = 0;i < n;i++){
            modfy(root,num[i]);
            int s = quarry(root,min,num[i]-1);
            if (i != n-1)
                System.out.print(s+" ");
            else
                System.out.println(s);
        }
    }

    public static void main(String[] args){
        init();
    }
}