Golang每日一练(leetDay0103) 区域和检索1~3

package main
import "fmt"
type NumArray struct {
  prefixSum []int
}
func Constructor(nums []int) NumArray {
  n := len(nums)
  prefixSum := make([]int, n+1)
  for i := 0; i < n; i++ {
    prefixSum[i+1] = prefixSum[i] + nums[i]
  }
  return NumArray{prefixSum}
}
func (this *NumArray) SumRange(left int, right int) int {
  // 返回区间和
  return this.prefixSum[right+1] - this.prefixSum[left]
}
func main() {
  nums := []int{-2, 0, 3, -5, 2, -1}
  obj := Constructor(nums)
  fmt.Println(obj.SumRange(0, 2))
  fmt.Println(obj.SumRange(2, 5))
  fmt.Println(obj.SumRange(0, 5))
}

package main
import "fmt"
type NumMatrix struct {
  prefixSum [][]int
}
func Constructor(matrix [][]int) NumMatrix {
  m, n := len(matrix), len(matrix[0])
  prefixSum := make([][]int, m+1)
  for i := range prefixSum {
    prefixSum[i] = make([]int, n+1)
  }
  for i := 1; i <= m; i++ {
    for j := 1; j <= n; j++ {
      prefixSum[i][j] = matrix[i-1][j-1] + prefixSum[i][j-1] + prefixSum[i-1][j] - prefixSum[i-1][j-1]
    }
  }
  return NumMatrix{prefixSum}
}
func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
  return this.prefixSum[row2+1][col2+1] - this.prefixSum[row2+1][col1] - this.prefixSum[row1][col2+1] + this.prefixSum[row1][col1]
}
func main() {
  numMatrix := [][]int{
    {3, 0, 1, 4, 2},
    {5, 6, 3, 2, 1},
    {1, 2, 0, 1, 5},
    {4, 1, 0, 1, 7},
    {1, 0, 3, 0, 5}}
  obj := Constructor(numMatrix)
  fmt.Println(obj.SumRegion(2, 1, 4, 3))
  fmt.Println(obj.SumRegion(1, 1, 2, 2))
  fmt.Println(obj.SumRegion(1, 2, 2, 4))
}

package main
import "fmt"
type NumArray struct {
  tree []int
  n    int
}
func Constructor(nums []int) NumArray {
  n := len(nums)
  tree := make([]int, n*4)
  if n > 0 {
    buildTree(tree, nums, 1, 0, n-1)
  }
  return NumArray{tree, n}
}
func buildTree(tree []int, nums []int, node, start, end int) {
  if start == end {
    tree[node] = nums[start]
    return
  }
  mid := start + (end-start)/2
  leftNode, rightNode := node*2, node*2+1
  buildTree(tree, nums, leftNode, start, mid)
  buildTree(tree, nums, rightNode, mid+1, end)
  tree[node] = tree[leftNode] + tree[rightNode]
}
func (this *NumArray) Update(index int, val int) {
  updateTree(this.tree, 1, 0, this.n-1, index, val)
}
func updateTree(tree []int, node, start, end, index, val int) {
  if start == end {
    tree[node] = val
    return
  }
  mid := start + (end-start)/2
  leftNode, rightNode := node*2, node*2+1
  if index <= mid {
    updateTree(tree, leftNode, start, mid, index, val)
  } else {
    updateTree(tree, rightNode, mid+1, end, index, val)
  }
  tree[node] = tree[leftNode] + tree[rightNode]
}
func (this *NumArray) SumRange(left int, right int) int {
  return queryTree(this.tree, 1, 0, this.n-1, left, right)
}
func queryTree(tree []int, node, start, end, left, right int) int {
  if start > right || end < left {
    return 0
  }
  if start >= left && end <= right {
    return tree[node]
  }
  mid := start + (end-start)/2
  leftSum := queryTree(tree, node*2, start, mid, left, right)
  rightSum := queryTree(tree, node*2+1, mid+1, end, left, right)
  return leftSum + rightSum
}
func main() {
  numArray := []int{1, 3, 5}
  obj := Constructor(numArray)
  fmt.Println(obj.SumRange(0, 2))
  obj.Update(1, 2)
  fmt.Println(obj.SumRange(0, 2))
}