Link

题意

分析

单点修改板题。

代码

package main

type seg []struct {
    l, r int
    val  int
}

func (t seg) pushUp(cur int) {
    t[cur].val = t[cur<<1].val + t[cur<<1|1].val
}

// 注意a下标从0开始, 但是l, r从1开始，且线段树下标从1开始
func (t seg) build(a []int, cur, l, r int) {
    t[cur].l, t[cur].r = l, r
    if l == r {
        t[cur].val = a[l-1] // 注意a数组下标从0开始，所以l-1
        return
    }
    mid := (l + r) >> 1
    t.build(a, cur<<1, l, mid)
    t.build(a, cur<<1|1, mid+1, r)
    t.pushUp(cur)
}

func (t seg) query(cur, l, r int) int {
    // 这个节点，已经被完全包含在 查询区间[l,r]之间了
    if l <= t[cur].l && t[cur].r <= r {
        return t[cur].val
    }
    mid := (t[cur].l + t[cur].r) >> 1
    //和右区间没关系 ,直接去左边查找 [0,4]  qR <= 2 [0,2]之间查找
    if r <= mid {
        return t.query(cur<<1, l, r)
    } else if l >= mid+1 {
        //和左区间没有关系，直接去右边查找 [0,4] qL > 2  --> [3,4]
        return t.query(cur<<1|1, l, r)
    } else {
        // 两边的都去查，然后合并
        return t.query(cur<<1, l, r) + t.query(cur<<1|1, l, r)
    }
}

// 单点修改
func (t seg) update(cur, i, val int) {
    if t[cur].l == t[cur].r {
        t[cur].val = val
        return
    }
    if mid := (t[cur].l + t[cur].r) >> 1; i <= mid {
        t.update(cur<<1, i, val)
    } else {
        t.update(cur<<1|1, i, val)
    }
    t.pushUp(cur)
}

type NumArray struct {
    t seg
}

func Constructor(nums []int) NumArray {
    t := make(seg, 4*len(nums))
    t.build(nums, 1, 1, len(nums))
    return NumArray{t}
}

// Update 单点修改
// 注意index+1, 因为线段树下标从1开始
func (this *NumArray) Update(index int, val int) {
    this.t.update(1, index+1, val)
}

// SumRange 注意left和right+1, 因为线段树下标从1开始
func (this *NumArray) SumRange(left int, right int) int {
    return this.t.query(1, left+1, right+1)
}

动态开点版：

package main

type SegNode struct {
    lc, rc *SegNode
    l, r   int
    sum    int64
}

func (o *SegNode) pushUp() {
    o.sum = o.lc.sum + o.rc.sum
}

func (o *SegNode) build(a []int, l, r int) {
    o.l, o.r = l, r
    if l == r {
        o.sum = int64(a[l-1])
        return
    }
    m := (l + r) >> 1
    o.lc = &SegNode{}
    o.lc.build(a, l, m)
    o.rc = &SegNode{}
    o.rc.build(a, m+1, r)
    o.pushUp()
}

func (o *SegNode) update(i int, add int64) {
    if o.l == o.r {
        o.sum = add
        return
    }
    m := (o.l + o.r) >> 1
    if i <= m {
        if o.lc == nil {
            o.lc = &SegNode{l: o.l, r: m}
        }
        o.lc.update(i, add)
    } else {
        if o.rc == nil {
            o.rc = &SegNode{l: m + 1, r: o.r}
        }
        o.rc.update(i, add)
    }
    o.pushUp()
}

func (o *SegNode) query(l, r int) int64 {
    if o == nil || l > o.r || r < o.l {
        return 0
    }
    if l <= o.l && o.r <= r {
        return o.sum
    }
    m := (o.l + o.r) >> 1
    if r <= m {
        return o.lc.query(l, r)
    }
    if l > m {
        return o.rc.query(l, r)
    }
    return o.lc.query(l, r) + o.rc.query(l, r)
}

type NumArray struct {
    seg *SegNode
}

func Constructor(nums []int) NumArray {
    seg := &SegNode{}
    seg.build(nums, 1, len(nums))
    return NumArray{seg}
}

// Update 单点修改
// 注意index+1, 因为线段树下标从1开始
func (this *NumArray) Update(index int, val int) {
    this.seg.update(index+1, int64(val))
}

// SumRange 注意left和right+1, 因为线段树下标从1开始
func (this *NumArray) SumRange(left int, right int) int {
    return int(this.seg.query(left+1, right+1))
}