Segment Tree — Range Queries in O(log N)

int[] tree = new int[4 * n];
void build(int node, int start, int end, int[] arr) {
  if (start == end) { tree[node] = arr[start]; return; }
  int mid = (start + end) / 2;
  build(2*node, start, mid, arr);
  build(2*node+1, mid+1, end, arr);
  tree[node] = tree[2*node] + tree[2*node+1];
}

long query(int node, int start, int end, int l, int r) {
  if (r < start || end < l) return 0;
  if (l <= start && end <= r) return tree[node];
  int mid = (start + end) / 2;
  return query(2*node, start, mid, l, r) + query(2*node+1, mid+1, end, l, r);
}

void update(int node, int start, int end, int idx, int val) {
  if (start == end) { tree[node] = val; return; }
  int mid = (start + end) / 2;
  if (idx <= mid) update(2*node, start, mid, idx, val);
  else update(2*node+1, mid+1, end, idx, val);
  tree[node] = tree[2*node] + tree[2*node+1];
}

int[] tree = new int[4 * n];
void build(int node, int start, int end, int[] arr) {
  if (start == end) { tree[node] = arr[start]; return; }
  int mid = (start + end) / 2;
  build(2*node, start, mid, arr);
  build(2*node+1, mid+1, end, arr);
  tree[node] = tree[2*node] + tree[2*node+1];
}

long query(int node, int start, int end, int l, int r) {
  if (r < start || end < l) return 0;
  if (l <= start && end <= r) return tree[node];
  int mid = (start + end) / 2;
  return query(2*node, start, mid, l, r) + query(2*node+1, mid+1, end, l, r);
}

void update(int node, int start, int end, int idx, int val) {
  if (start == end) { tree[node] = val; return; }
  int mid = (start + end) / 2;
  if (idx <= mid) update(2*node, start, mid, idx, val);
  else update(2*node+1, mid+1, end, idx, val);
  tree[node] = tree[2*node] + tree[2*node+1];
}