Segment vs Fenwick

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <queue>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>

#define INF 1000000000
#define FOR(i, a, b) for(int i=int(a); i<int(b); i++)
#define FORC(cont, it) for(decltype((cont).begin()) it = (cont).begin(); it != (cont).end(); it++)
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

#define maxN 100000
#define maxQ 100000
#define tests 10000

struct Query {
    int type, l, r;
};

int N, Q;
ll segTree[2 * maxN], bit[maxN+1], a[maxN], ansSeg[maxQ], ansBit[maxQ];
Query q[maxQ];

ll querySeg(int l, int r) { // [l,r)
    ll ans = 0;
    for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
        if (l & 1) ans += segTree[l++];
        if (r & 1) ans += segTree[--r];
    }
    return ans;
}

void modifySeg(int n, int m) {
    segTree[n += N] += m;
    while (n >>= 1) {
        segTree[n] = segTree[n << 1] + segTree[n << 1 | 1];
    }
}

ll queryFenwick(int l) {
    ll sum = 0;
    while (l) {
        sum += bit[l];
        l -= (l & -l);
    }
    return sum;
}

void modifyFenwick(int n, ll m) {
    while (n <= N) {
        bit[n] += m;
        n += n & -n;
    }
}

int main() {
    double totalSeg = 0, totalFenwick = 0;
    FOR(test, 0, tests) {
        // Generate random case
        N = rand() % maxN;
        Q = rand() % maxQ;
        FOR(i, 0, N) {
            a[i] = (ll)rand()<<16 | rand();
        }
        FOR(i, 0, Q) {
            q[i].type = rand() & 1;
            q[i].l = rand() % N;
            if (q[i].type) {
                q[i].r = rand() % N;
                if (q[i].l > q[i].r) swap(q[i].l, q[i].r);
            }
            else {
                q[i].r = rand();
            }
        }

        // Start Segment tree
        clock_t t = clock();

        // Initialization
        FOR(i, 0, N) segTree[i + N] = a[i];
        for (int i = N - 1; i; i--) segTree[i] = segTree[i << 1] + segTree[i << 1 | 1];

        // Queries
        FOR(i,0,Q) {
            if (q[i].type) ansSeg[i] = querySeg(q[i].l, q[i].r + 1);
            else modifySeg(q[i].l, q[i].r), ansSeg[i] = 0;
        }

        double testTime = (float)(clock() - t)/CLOCKS_PER_SEC;
        //printf("Segment tree: %.3f\n", testTime);
        totalSeg += testTime;
        // End Segment Tree

        // Start Fenwick
        t = clock();

        // Initialization
        memset(bit, 0, sizeof(bit));
        FOR(i,1,N+1) {
            modifyFenwick(i, a[i - 1]);
        }

        // Queries
        FOR(i, 0, Q) {
            if (q[i].type) ansBit[i] = queryFenwick(q[i].r + 1) - queryFenwick(q[i].l);
            else {
                modifyFenwick(q[i].l + 1, q[i].r);
                ansBit[i] = 0;
            }
        }

        testTime = (float)(clock() - t) / CLOCKS_PER_SEC;
        //printf("Fenwick tree: %.3f\n", testTime);
        totalFenwick += testTime;
        // End Fenwick

        // To make sure my code is not bugged :)
        FOR(i, 0, Q) {
            if (ansBit[i] != ansSeg[i]) {
                printf("Something is wrong =(\n");
            }
        }
    }
    printf("Total Segment tree: %.3f\n", totalSeg);
    printf("Total Fenwick tree: %.3f\n", totalFenwick);
    return 0;
}