fenwick.cpp

#pragma GCC optimize("03")
#pragma GCC target("avx2")

#include <bits/stdc++.h>
using namespace std;

const int logn = 20;
const int n = (1<<logn), m = 1e5;
int t[n], q[m], res[m], rs[m];

int sum(int r) {
    int res = 0;
    for (; r > 0; r -= r & -r)
        res += t[r];
    return res;
}

void timeit(void (*f)()) {
    clock_t start = clock();
    for (int i = 0; i < 1000; i++)
        f();
    cout << double(clock() - start) / CLOCKS_PER_SEC << endl;
}

void fenwick1() {
    for (int i = 0; i < m; i++)
        res[i] = sum(q[i]);
}

void fenwick2() {
    memcpy(rs, q, sizeof q);
    for (int l = 0; l < logn; l++) {
        for (int i = 0; i < m; i++) {
            int x = rs[i];
            res[i] += t[x];
            x -= (x & -x);
            rs[i] = x;
        }
    }
}

int main() {
    for (int i = 0; i < m; i++)
        q[i] = rand() % n;

    timeit(fenwick1);
    timeit(fenwick2);

    return 0;
}