type SegTreeNode struct {
    lazy  int
    val   int
    left  *SegTreeNode
    right *SegTreeNode
}

type SegTree struct {
    //線段樹的范圍，0~N
    N    int
    root *SegTreeNode
}
 
// 創(chuàng)建線段樹
func CreateSegTree(n int) *SegTree {
    return &SegTree{
        N: n,
        root: &SegTreeNode{
            lazy:  0,
            val:   0,
            left:  nil,
            right: nil,
        },
    }
}

// 遞歸上推
func (ST *SegTree) Pushup(node *SegTreeNode) {
    node.val = node.left.val + node.right.val
}

// 同步下推
func (ST *SegTree) Pushdown(node *SegTreeNode, leftnum, rightnum int) {
    //創(chuàng)建左右節(jié)點(diǎn)
    if node.left == nil {
        node.left = new(SegTreeNode)
    }
    if node.right == nil {
        node.right = new(SegTreeNode)
    }
    //下推節(jié)點(diǎn)懶惰標(biāo)記
    if node.lazy == 0 {
        return
    }
    node.left.val += leftnum * node.lazy
    node.right.val += rightnum * node.lazy
    //下推
    node.left.lazy += node.lazy
    node.right.lazy += node.lazy
    //置零
    node.lazy = 0
}

// 更新操作，更新[left,right]區(qū)間的值，start和end是當(dāng)前處在區(qū)間
func (ST *SegTree) Update(node *SegTreeNode, start, end, left, right, val int) {
    if left <= start && end <= right {
        //鎖定區(qū)間，進(jìn)行更新
        node.val += (end - start + 1) * val
        node.lazy += val
        return
    }
    //縮小區(qū)間
    mid := (start + end) / 2
    //需要找到子節(jié)點(diǎn)，先下推懶惰標(biāo)記
    ST.Pushdown(node, mid-start+1, end-mid)
    if mid >= left {
        ST.Update(node.left, start, mid, left, right, val)
    }
    if mid+1 <= right {
        ST.Update(node.right, mid+1, end, left, right, val)
    }
    //遞歸
    ST.Pushup(node)
}

// 查詢操作，返回區(qū)間的值
func (ST *SegTree) Query(node *SegTreeNode, start, end, left, right int) int {
    if left <= start && end <= right {
        return node.val
    }
    mid := (start + end) / 2
    ST.Pushdown(node, mid-start+1, end-mid)
    ans := 0
    if left <= mid {
        ans += ST.Query(node.left, start, mid, left, right)
    }
    if mid+1 <= right {
        ans += ST.Query(node.right, mid+1, end, left, right)
    }
    return ans
}