Как Фенвиком найти для каждого элемента число меньших справа (count of smaller after self)?

Идём справа налево и поддерживаем BIT частот по сжатым значениям уже виденных (то есть тех, что правее текущего). Для a[i] ответ — количество добавленных элементов со значением строго меньше a[i], то есть query(rank(a[i]) - 1).

vector<int> countSmallerAfter(vector<int> a){
    int n = a.size();
    vector<int> srt(a);
    sort(srt.begin(), srt.end());
    srt.erase(unique(srt.begin(), srt.end()), srt.end());
    auto rank = [&](int x){
        return int(lower_bound(srt.begin(), srt.end(), x) - srt.begin()) + 1;
    };
    BIT bit((int)srt.size());
    vector<int> res(n);
    for (int i = n - 1; i >= 0; --i) {
        int r = rank(a[i]);
        res[i] = (int)bit.query(r - 1); // строго меньших среди правых
        bit.update(r, 1);               // теперь a[i] тоже «правее» для следующих
    }
    return res;
}

Ключ — query(r - 1): это сумма частот всех значений с рангом меньше r, то есть строго меньших a[i] (равные имеют тот же ранг и не учитываются). Сложность: сжатие O(n log n), основной цикл O(n log n), память O(n). Если нужно «строго больше справа» — берите (добавлено) - query(r) по аналогии с инверсиями.