let n = 8

let st = Array.make (4 * n) 0

let rec build a l r node =
  if l = r then st.(node) <- a.(l)
  else begin
    let mid = (l + r) / 2 in
    build a l mid (2 * node);
    build a (mid + 1) r (2 * node + 1);
    st.(node) <- st.(2 * node) + st.(2 * node + 1)
  end

let rec query l r ql qr node =
  if qr < l || ql > r then 0
  else if ql <= l && r <= qr then st.(node)
  else begin
    let mid = (l + r) / 2 in
    query l mid ql qr (2 * node) + query (mid + 1) r ql qr (2 * node + 1)
  end

let rec update l r idx delta node =
  if l = r then st.(node) <- st.(node) + delta
  else begin
    let mid = (l + r) / 2 in
    if idx <= mid then update l mid idx delta (2 * node)
    else update (mid + 1) r idx delta (2 * node + 1);
    st.(node) <- st.(2 * node) + st.(2 * node + 1)
  end

;;

let a = [| 1; 3; 5; 7; 9; 11; 13; 15 |] in
build a 0 (n - 1) 1;
let r1 = query 0 (n - 1) 2 5 1 in
update 0 (n - 1) 3 10 1;
let r2 = query 0 (n - 1) 2 5 1 in
r1 + r2 * 100
