Leetcode - Remove Element
Leetcode - Trapping Rain Water

Leetcode - Range Sum Query - Mutable

violet posted @ Mar 30, 2020 01:34:43 AM in 算法 with tags Algorithm Golang SegmentTree , 282 阅读

https://leetcode.com/problems/range-sum-query-mutable/

Given an integer array nums, find the sum of the elements between indices i and j (ij), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

 

This is a typical segment tree usage. It should be recited.

type NumArray struct {
    root *SegmentTree
}

type SegmentTree struct {
    start int
    end int
    left *SegmentTree
    right *SegmentTree
    sum int
}

func Constructor(nums []int) NumArray {
    return NumArray{
        root: buildTree(nums, 0, len(nums)-1),
    }
}

func buildTree(nums []int, start, end int) *SegmentTree {
    if start > end {
        return nil
    }
    result := &SegmentTree{
        start: start,
        end: end,
    }
    if start == end {
        result.sum = nums[start]
        return result
    }
    mid := (start+end)/2
    result.left = buildTree(nums, start, mid)
    result.right = buildTree(nums, mid+1, end)
    result.sum = result.left.sum + result.right.sum
    
    return result
}


func (this *NumArray) Update(i int, val int)  {
    update(this.root, i, val)
}

func update(root *SegmentTree, pos, val int) {
    if root.start == root.end {
        root.sum = val
        return
    }
    mid := (root.start + root.end)/2
    if pos <= mid {
        update(root.left, pos, val)
    } else {
        update(root.right, pos, val)
    }
    root.sum = root.left.sum + root.right.sum
}


func (this *NumArray) SumRange(i int, j int) int {
    return sumRange(this.root, i, j)
}

func sumRange(root *SegmentTree, start, end int) int {
    if root.start == start && root.end == end {
        return root.sum
    }
    mid := (root.start+root.end)/2
    if end <= mid {
        return sumRange(root.left, start, end)
    } else if start > mid {
        return sumRange(root.right, start, end)
    } 
    return sumRange(root.left, start, mid) + sumRange(root.right, mid+1, end)    
}


/**
 * Your NumArray object will be instantiated and called as such:
 * obj := Constructor(nums);
 * obj.Update(i,val);
 * param_2 := obj.SumRange(i,j);
 */
https://www.li9.in/k 说:
Aug 18, 2022 02:15:57 PM

Karnataka PUC Question Paper 2023 Download – KSEEB 1st & 2nd PUC Important Question Paper 2023, The Department of Pre-University Education, https://www.li9.in/karnataka-sslc-question-paper-pdf/ Government of Karnataka PUE, has been announced the Previous Question Paper for II PUC examination for the year 2023. The examination will begin in the month of March 2023 and will continue till March last week 2023. IInd PUC Important Question Paper 2023

NCERT 4th Class Rev 说:
Sep 27, 2023 04:40:07 PM

The information Available in CBSE Class 4th new Syllabus 2024 is important for the Preparation of CBSE Class 4th Board Exams 2024, Online Service Covers All Subjects Published by NCERT Syllabus 2024 for class 4th in Hindi, English and Urdu medium Chapter Wise Pdf Format, our Website Providing the latest NCERT 4th Class Syllabus 2024 for all Important Subjects.NCERT 4th Class new Syllabus 2024 is Recently NCERT 4th Class Revised Syllabus 2024 Released by National Council of Educational Research and Training (NCERT) is an Autonomous Organisation set up in 1961 by the Government of India to Assist and Advise the Central and State Governments on Policies.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter