2021-05-15：数组为{3, 2, 2, 3, 1}，查询为(0, 3, 2)，意思是在数组里下标0~3这个范围上，有几个

package main

import "fmt"

func main() {
    arr := []int{3, 2, 2, 3, 1}
    box := NewQueryBox2(arr)
    ret := box.query(0, 3, 2)
    fmt.Println(ret)
}

type QueryBox2 struct {
    dataMap map[int][]int
}

func NewQueryBox2(arr []int) *QueryBox2 {
    ret := &QueryBox2{}
    ret.dataMap = make(map[int][]int)
    for i := 0; i < len(arr); i++ {
        ret.dataMap[arr[i]] = append(ret.dataMap[arr[i]], i)
    }
    return ret
}

func (this *QueryBox2) query(L int, R int, value int) int {
    if _, ok := this.dataMap[value]; !ok {
        return 0
    }
    indexArr := this.dataMap[value]
    // 查询 < L 的下标有几个
    a := this.countLess(indexArr, L)
    // 查询 < R+1 的下标有几个
    b := this.countLess(indexArr, R+1)
    return b - a
}

// 在有序数组arr中，用二分的方法数出<limit的数有几个
// 也就是用二分法，找到<limit的数中最右的位置
func (this *QueryBox2) countLess(arr []int, limit int) int {
    L := 0
    R := len(arr) - 1
    mostRight := -1
    for L <= R {
        mid := L + ((R - L) >> 1)
        if arr[mid] < limit {
            mostRight = mid
            L = mid + 1
        } else {
            R = mid - 1
        }
    }
    return mostRight + 1
}