2、树状数组

Leetcode 315. 计算右侧小于当前元素的个数

Leetcode 2426. 满足不等式的数对数目

树状数组模板 计算数对关系 统计比当前小的数的个数

$Python$ 的模板

def lowBit(self, x):
    return x & (-x)

def add(self, x):
    while x < len(self.tree):
        self.tree[x] += 1
        x += self.lowBit(x)

def update(self, x, v):
    while x < len(self.tree):
        self.tree[x] += v
        x += self.lowBit(x)

def query(self, k):
    res = 0
    while k > 0:
        res += self.tree[k]
        k -= self.lowBit(k)
    return res

$JAVA$ 的模板

int[] tree = new int[10000010];
public int lowBit(int x) {
    return x & (-x);
}

public void add(int x) {
    while (x < tree.length) {
        ++tree[x];
        x += lowBit(x);
    }
}

public void update(int x, int v) {
    while (x < tree.length) {
        tree[x] += v;
        x += lowBit(x);
     }
}

public int query(int k) {
    int res = 0;
    while (k > 0) {
        res += tree[k];
        k -= lowBit(k);
    }
    return res;
}