树状数组

重点
1. 两种操作：单点修改，区间求和，维护一个前缀和序列
2. 想到了如何求牛的身高，但是没能看透两种操作的本质

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
using namespace std;
const int N = 100010;
int n;
int tr[N], a[N], b[N];

int lowbit(int x) {
    return x & -x;
}

void add(int x, int c) {
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

int sum(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

int main() {
    cin >> n;
    a[1] = 0;
    for (int i = 2; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; i++) {
        add(i, 1);
    }
    for (int i = n; i; i--) {
        int l = 1, r = n; 
        while (l < r) {
            int mid = (l + r) >> 1;
            if (sum(mid) >= a[i] + 1) r = mid;
            else l = mid + 1;
        }
        b[i] = l;
        add(l, -1);
    }
    for (int i = 1; i <= n; i++) printf("%d\n", b[i]);

    return 0;
}