LeetCode5564

给你一个整数数组 instructions ，你需要根据 instructions 中的元素创建一个有序数组。一开始你有一个空的数组 nums ，你需要 从左到右 遍历 instructions 中的元素，将它们依次插入 nums 数组中。每一次插入操作的 代价 是以下两者的 较小值 ：

nums 中 严格小于 instructions[i] 的数字数目。 nums 中 严格大于 instructions[i] 的数字数目。 比方说，如果要将 3 插入到 nums = [1,2,3,5] ，那么插入操作的 代价 为 min(2, 1) (元素 1 和 2 小于 3 ，元素 5 大于 3 ），插入后 nums 变成 [1,2,3,3,5] 。

请你返回将 instructions 中所有元素依次插入 nums 后的 总最小代价 。由于答案会很大，请将它对 109 + 7 取余 后返回

周赛第四题，用的线段树/树状数组结构（多用于高效计算数列的前缀和），记录一下模板，不得不说这思想真的太妙了 最简单的树状数组定义的两个操作 1、查询：查询任意的区间和（或者其它区间操作） 2、更新：对元素进行更新（涉及修改区间和大小）

预备知识：lowbit函数：返回最后一个1的位置所代表的数值

def lowbit(x):
	return x & (-x)

2、更新树状数组

def update(node, x):
	while node <= n # n为数组长度
		tree[node] += x
		node += lowbit(node)

3、查询树状数组

def query(node):
	temp = 0
	while node > 0:
		temp += tree[node]
		x -= lowbit(node)
	return temp

上述题目题解：

def lowbit(x):
	return x & (-x)

def update(x):
    while x <= n:
        tree[x] += 1
        x += lowbit(x)

def query(x):
    temp = 0
    while x > 0:
        temp += tree[x]
        x -= lowbit(x)
    return temp

n = max(instructions)
tree = [0 for _ in range(n+1)]
res = 0
for i in range(len(instructions)):
    res = res + min(query(instructions[i]-1), i - query(instructions[i]))
    update(instructions[i])
return res % (10**9 + 7)