#include <iostream>
#include <random>
#include <ctime>
#include <cassert>
#include <immintrin.h>


const int Q = 30000000;
const int N = 1 << 24;


using T = uint32_t;
T a[2 * N];
T pref[N];


const T identity_element = 0;
T reduce(T a, T b) {
	return a + b;
}
__attribute__((target("sse4.1"))) __m128i reduce(__m128i a, __m128i b) {
	return _mm_add_epi32(a, b);
}
__attribute__((target("avx2"))) __m256i reduce(__m256i a, __m256i b) {
	return _mm256_add_epi32(a, b);
}

static_assert(sizeof(T) == 4, "Segment tree elements must be 32-bit");


T query_recursive_inner(int v, int vl, int vr, int l, int r) {
	if(l >= r) {
		return identity_element;
	}
	if(l <= vl && vr <= r) {
		return a[v];
	}
	int vm = (vl + vr) / 2;
	return reduce(query_recursive_inner(v * 2, vl, vm, l, std::min(r, vm)), query_recursive_inner(v * 2 + 1, vm, vr, std::max(l, vm), r));
}
T query_recursive_inner(int l, int r) {
	return query_recursive_inner(1, 0, N, l, r + 1);
}


T query_recursive_outer(int v, int vl, int vr, int l, int r) {
	if(vl == l && vr == r) {
		return a[v];
	} else {
		int vm = (vl + vr) / 2;
		if(r <= vm) {
			return query_recursive_outer(v * 2, vl, vm, l, r);
		} else if(l >= vm) {
			return query_recursive_outer(v * 2 + 1, vm, vr, l, r);
		} else {
			return reduce(query_recursive_outer(v * 2, vl, vm, l, vm), query_recursive_outer(v * 2 + 1, vm, vr, vm, r));
		}
	}
}
T query_recursive_outer(int l, int r) {
	return query_recursive_outer(1, 0, N, l, r + 1);
}


T query_bottom_up(int l, int r) {
	l += N;
	r += N;
	T ans = identity_element;
	while(l <= r) {
		if(l & 1) {
			ans = reduce(ans, a[l]);
			l++;
		}
		if(!(r & 1)) {
			ans = reduce(ans, a[r]);
			r--;
		}
		l /= 2;
		r /= 2;
	}
	return ans;
}


int ffs(unsigned int x) {
	return sizeof(unsigned int) * 8 - 1 - __builtin_clz(x);
}


__attribute__((target("avx2"))) T query_parallel(int l, int r) {
	if(l == r) {
		return a[l + N];
	}

	int mbit = ffs(l ^ r);
	int reset = ((1 << mbit) - 1);
	int m = r & ~reset;

	using vecint = T __attribute__((vector_size(32)));
	__m256i identity_vec = _mm256_set1_epi32(identity_element);
	vecint vec_ans = (vecint)identity_vec;
	__m256i indexes = _mm256_set_epi32(7, 6, 5, 4, 3, 2, 1, 0);

	if((l & reset) != 0) {
		int ll = l - 1 + N;
		int rr = m - 1 + N;

		int modbit = 0;
		int maxmodbit = ffs(ll ^ rr) + 1;

		vecint ll_vec = (vecint)_mm256_srav_epi32(_mm256_set1_epi32(ll), indexes);

#define LOOP(content) if(modbit + 8 <= maxmodbit) { \
			vec_ans = (vecint)reduce((__m256i)vec_ans, _mm256_i32gather_epi32((int*)a, (__m256i)(((ll_vec & 1) - 1) & (ll_vec | 1)), 4)); \
			ll_vec >>= 8; \
			modbit += 8; \
			content \
		}
		LOOP(LOOP(LOOP(LOOP())))
#undef LOOP

		__m256i tmp = _mm256_i32gather_epi32((int*)a, (__m256i)(((ll_vec & 1) - 1) & (ll_vec | 1)), 4);
		__m256i mask = _mm256_cmpgt_epi32(_mm256_set1_epi32(maxmodbit & 7), indexes);
		vec_ans = (vecint)reduce((__m256i)vec_ans, _mm256_blendv_epi8(identity_vec, tmp, mask));
	} else {
		vec_ans[0] = reduce(vec_ans[0], a[(l + N) >> mbit]);
	}

	if((r & reset) != reset) {
		int ll = m + N;
		int rr = r + 1 + N;

		int modbit = 0;
		int maxmodbit = ffs(ll ^ rr) + 1;

		vecint rr_vec = (vecint)_mm256_srav_epi32(_mm256_set1_epi32(rr), indexes);

#define LOOP(content) if(modbit + 8 <= maxmodbit) { \
			vec_ans = (vecint)reduce((__m256i)vec_ans, _mm256_i32gather_epi32((int*)a, (__m256i)(~((rr_vec & 1) - 1) & (rr_vec - 1)), 4)); \
			rr_vec >>= 8; \
			modbit += 8; \
			content \
		}
		LOOP(LOOP(LOOP(LOOP())))
#undef LOOP

		__m256i tmp = _mm256_i32gather_epi32((int*)a, (__m256i)(~((rr_vec & 1) - 1) & (rr_vec - 1)), 4);
		__m256i mask = _mm256_cmpgt_epi32(_mm256_set1_epi32(maxmodbit & 7), indexes);
		vec_ans = (vecint)reduce((__m256i)vec_ans, _mm256_blendv_epi8(identity_vec, tmp, mask));
	} else {
		vec_ans[0] = reduce(vec_ans[0], a[(r + N) >> mbit]);
	}

	// vec_ans = 7 6 5 4 3 2 1 0
    __m128i low128 = _mm256_castsi256_si128((__m256i)vec_ans); // 3 2 1 0
    __m128i high128 = _mm256_extractf128_si256((__m256i)vec_ans, 1); // 7 6 5 4
    __m128i ans128 = reduce(low128, high128); // 7+3 6+2 5+1 4+0
    T ans = identity_element;
    for(int i = 0; i < 4; i++) {
    	ans = reduce(ans, ((T __attribute__((vector_size(16))))ans128)[i]);
    }
    return ans;
}


T query_prefix(int l, int r) {
	return pref[r] - (l == 0 ? 0 : pref[l - 1]);
}


int main() {
	std::pair<int, int>* queries = new std::pair<int, int>[Q];
	for(int i = 0; i < Q; i++) {
		int l = rand() % N;
		int r = rand() % N;
		if(l > r) {
			std::swap(l, r);
		}
		queries[i] = {l, r};
	}
	for(int i = 0; i < N; i++) {
		a[N + i] = rand();
	}
	for(int i = N - 1; i >= 1; i--) {
		a[i] = reduce(a[i * 2], a[i * 2 + 1]);
	}
	a[0] = identity_element;

	for(int i = 0; i < N; i++) {
		pref[i] = (i == 0 ? 0 : pref[i - 1]) + a[N + i];
	}

#define CHECK(func) { \
		auto clock_start = clock(); \
		T checksum = 0; \
		for(int i = 0; i < Q; i++) { \
			checksum += func(queries[i].first, queries[i].second); \
		} \
		std::cout << #func << ": " << (double)(clock() - clock_start) / CLOCKS_PER_SEC << " seconds (checksum: " << checksum << ")" << std::endl; \
	}

	CHECK(query_recursive_inner)
	CHECK(query_recursive_outer)
	CHECK(query_bottom_up)
	CHECK(query_parallel)
	CHECK(query_prefix)

	return 0;
}