package main

import "fmt"
type Node struct {
	// 左右区间
	left *Node
	right *Node

	value int
	// 懒标记
	add int
}

// 懒标记下推
func (n *Node) PushDown(leftCnt, rightCnt int) {
	// 若不存在左右节点，创建之
	if n.left == nil {
		n.left = &Node{}
	}
	if n.right == nil {
		n.right = &Node{}
	}

	// 若不存在懒标记，退出
	if n.add == 0 {
		return
	}

	// 存在懒标记，下推至左右节点，并清除自身的懒标记
  // 若是区间覆盖操作，则value与add都不需要累加
  // 若是区间加减操作，则value与add都需要累加
	n.left.value += n.add * leftCnt // 求区间和时，需要给value加上对应区间节点个数*懒标记值。若求最值，则只需加上懒标记值
	n.right.value += n.add * rightCnt
	n.left.add += n.add
	n.right.add += n.add
	n.add = 0
}

// 数据聚合
func (n *Node) PushUp() {
	// 可根据【求区间和】或【求区间最值】的场景更换代码
	n.value = n.left.value + n.right.value
}

// 区间更新操作，delta为对区间的操作数值
func (n *Node) _update(l, r int, delta int, s, e int) {
	// 若当前段（[s,e]）位于更新区间（[l,r]），则直接更新value、add
	if s >= l && e <= r {
    // 若是区间覆盖操作，则value与add都不需要累加
    // 若是区间加减操作，则value与add都需要累加
		n.value += delta * (e-s+1) // 求区间和时，需要加上区间内节点数量*delta。若是求区间最值，则只需要加delta
		n.add += delta
		return
	}
	m := s + (e-s) >> 1
	// 尝试下推，左区间节点数为m-s+1，右区间节点数为e-m
	n.PushDown(m-s+1, e-m)
	// 更新左区间
	if l <= m {
		n.left._update(l, r, delta, s, m)
	}
	// 更新右区间
	if r > m {
		n.right._update(l, r, delta, m+1, e)
	}
	// 数据聚合
	n.PushUp()
}

// 区间查询操作
func (n *Node) _query(l, r int, s, e int) int {
	// 若当前段（[s,e]）位于查询区间（[l,r]），则直接返回
	if s >= l && e <= r {
		return n.value
	}
	m := s + (e-s) >> 1
	// 尝试下推，左区间节点数为m-s+1，右区间节点数位e-m
	n.PushDown(m-s+1, e-m)
	sum := 0
	// 查询左区间
	if l <= m {
		sum += n.left._query(l, r, s, m) // 若求最值，需替换逻辑
	}
	if r > m {
		sum += n.right._query(l, r, m+1, e)
	}
	return sum
}

func (n *Node) Update(l, r int, delta int) {
	n._update(l, r, delta, 0, int(1e9))
}

func (n *Node) Query(l, r int) int {
	return n._query(l, r, 0, int(1e9))
}

func Constructor(nums []int) Node {
	n := Node{}
	for i := range nums {
		n.Update(i,i, nums[i])
	}
	return n
}

func main() {
	root := Constructor([]int{1,2,3,4,5})
	fmt.Println(root.Query(0,4)) // 输出15
	root.Update(0, 2, 1)
	fmt.Println(root.Query(0,4)) // 输出18
	fmt.Println(root.Query(0,2)) // 输出9
}