how to make a segment tree in c++
#include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; bool isPower(long long n) { long long f = 1; while (f <= n) { if (f == n) { return false; } else { f *= 2; } } return true; } int main() { long long n; long long t; cin >> n >> t; vector<unsigned long long>v(n * 2); long long k; for (long long i = n; i < n*2; i++) { cin >> k; v[i] = k; } for (long long i = n - 1; i > 0; i--) { v[i] = v[2 * i] + v[2 * i + 1]; } unsigned long long i; unsigned long long j; unsigned long long x = 1; unsigned long long sum = 0; unsigned long long sum1 = 0; long long zz; for (long long l = 0; l < t; l++) { sum = 0; x = 1; sum1 = 0; cin >> i; cin >> j; i += n - 1; j += n - 1; zz = i; if (i == j) { cout << v[j] << endl; } else { while (isPower(i)) { if ((i) % 2 == 0) { sum += v[i]; i = i * x - 1; x = 1; } else { x = x * 2; i = i / 2; } } sum += v[i]; x = 1; while (isPower(j)) { if (j % 2 == 0) { sum1 += v[j]; j = j * x - 1; x = 1; } else { x = x * 2; j = j / 2; } } sum1 += v[j]; cout << (sum1 - sum + v[zz])% 9223372036854775807 << endl; } } }
Source: cses.fi