simple segment tree

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
template <class Key, class Compare = less<Key>>
using Tree = __gnu_pbds::tree<Key, __gnu_pbds::null_type, Compare, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;





int m, n; // n is smallest power of 2 bigger than m
vector<int> tree;

int sum(int a, int b, int k, int x, int y) {
  if (x > b || y < a) return 0;
  if (a <= x && y <= b) return tree[k];
  int d = (x + y) / 2;
  return sum(a, b, 2*k, x, d) + sum(a, b, 2*k+1, d+1, y);
}

void add(int k, int x) {
  k += n;
  tree[k] += x;
  for (k /= 2; k >= 1; k /= 2) {
    tree[k] = tree[2*k] + tree[2*k+1];
  }
}

void Main() {
  cin >> m;
  n = 1; while (n < m) n <<= 1;
  tree.resize(2*n+1, 0);
  for (int i = 0; i < m; ++i) {
    int x;
    cin >> x;
    add(i, x);
  }
//  for (int i = 1; i < 2*n; ++i) {
//    cout << setw(4) << i << ' ';
//  }
//  cout << '\n';
//  for (int i = 1; i < 2*n; ++i) {
//    cout << setw(4) << tree[i] << ' ';
//  }
//  cout << '\n';
  while (true) {
    int l, r;
    cin >> l >> r;
    int ans = sum(l, r, 1, 0, n-1);
    cout << "sum[" << l << ", " << r << "] = " << ans << '\n';
  }
}


int main() {
  ios::sync_with_stdio(false);
//  cin.tie(nullptr);
  #ifdef _DEBUG
//  freopen("in.txt", "r", stdin);
//  freopen("out.txt", "w", stdout);
  #endif
  Main();
  return 0;
}