Ruby Solution - Segment Tree
The first thing coming into my mind was RMQ. After some googling, I found this wonderful article.\n\n+ Range Minimum Query and Lowest Common Ancestor by danielp
The first thing coming into my mind was RMQ. After some googling, I found this wonderful article.\n\n+ [Range Minimum Query and Lowest Common Ancestor](https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/) by [danielp](https://www.topcoder.com/member-profile/danielp) (Note there are some typos or mistakes about the index)\n\nOther useful references:\n\n+ [LeetCode Solution of 307. Range Sum Query - Mutable](https://leetcode.com/articles/range-sum-query-mutable/)\n+ [A Recursive Approach to Segment Trees, Range Sum Queries & Lazy Propagation](https://leetcode.com/articles/recursive-approach-segment-trees-range-sum-queries-lazy-propagation/)\n\nHere is a summary about RMQ problems\n\n![0_1477451301199_upload-27fe6d52-3531-482b-a71e-67ba1be4c241](/uploads/files/1477451302993-upload-27fe6d52-3531-482b-a71e-67ba1be4c241.png) \n\nI use **Segment Tree** to pass the problem, which has a good support on updating.\n\n```ruby\nrequire 'minitest/autorun'\nrequire 'minitest/focus'\n\nclass NumArray\n  attr_reader :tree\n\n  def initialize(nums)\n    @tree = SegmentTree.new(nums)\n  end\n\n  def update(i, val)\n    tree.update(i, val)\n  end\n\n  def sum_range(i, j)\n    tree.query(i, j)\n  end\nend\n\n# Your NumArray object will be instantiated and called as such:\n# num_array = NumArray.new(nums)\n# num_array.sum_range(0, 1)\n# num_array.update(1, 10)\n# num_array.sum_range(0, 2)\n\n# This is a segment tree recording range sum as value\nclass SegmentTree\n  attr_reader :value, :data\n\n  def initialize(data)\n    @data = data.empty? ? [0] : data.clone\n    node_count = 2 * 2**( Math.log(@data.count,2).to_i + 1 )\n    @value = [0]*node_count\n\n    build(1, 0, @data.count-1)\n  end\n\n  def query(i, j)\n    recur_query(1, 0, data.count-1, i, j)\n  end\n\n  def update(i, val)\n    # puts "i: #{i} val: #{val} value: #{value.join(',')}"\n    gap = val - data[i]\n    data[i] = val\n\n    node = 1\n    b, e = 0, data.count-1\n    loop do\n      value[node] += gap\n\n      break if b == e && b == i\n\n      mid = (b+e)/2\n\n      if i <= mid\n        e = mid\n        node = 2*node\n      else\n        b = mid + 1\n        node = 2*node + 1\n      end\n    end\n  end\n\n  private\n\n    def build(node, b, e)\n      # puts "node: #{node} b: #{b} e: #{e}"\n\n      if b == e\n        return value[node] = data[b]\n      end\n\n      mid = (b+e)/2\n\n      value[node] = build(2*node, b, mid) + build(2*node+1, mid+1,  e)\n    end\n\n    def recur_query(node, b, e, i, j)\n      # if the current interval doesnot interset with the query interval\n      if i > e or j < b\n        return 0\n      end\n\n      # if the current interval is included in the query interval\n      if i <= b && e <= j\n        return value[node]\n      end\n\n      # compute the minimum position in the left and right part of current interval\n      mid = (b+e)/2\n      left  = recur_query(2*node,   b,      mid,  i, j)\n      right = recur_query(2*node+1, mid+1,  e,    i, j)\n\n      left + right\n    end\nend\n\nclass SegmentTreeTest < Minitest::Test\n  attr_reader :data, :tree\n\n  def setup\n    @data = [2,4,3,1,6,7,8,9,1,7]\n    @tree = SegmentTree.new(@data)\n  end\n\n  def test_query\n    assert_equal data[0..1].reduce(:+), tree.query(0, 1)\n    assert_equal data[1..5].reduce(:+), tree.query(1, 5)\n    assert_equal data[7..9].reduce(:+), tree.query(7, 9)\n  end\n\n  def test_update\n    tree.update(1, 10)\n    assert_equal 12, tree.query(0, 1)\n    assert_equal 27, tree.query(1, 5)\n\n    tree.update(9, 10)\n    assert_equal 20, tree.query(7, 9)\n  end\nend\n\nclass NumArrayTest < Minitest::Test\n  attr_reader :num_array\n  def setup\n    @num_array = NumArray.new( [2,4,3,1,6,7,8,9,1,7] )\n  end\n\n  def test_run\n    assert_equal 6,   num_array.sum_range(0, 1)\n    assert_equal 21,  num_array.sum_range(1, 5)\n    assert_equal 17,  num_array.sum_range(7, 9)\n\n    num_array.update(1, 10)\n    assert_equal 12, num_array.sum_range(0, 1)\n    assert_equal 27, num_array.sum_range(1, 5)\n\n    num_array.update(9, 10)\n    assert_equal 20, num_array.sum_range(7, 9)\n  end\n\n  def test_empty_data\n    assert_equal 0, NumArray.new( [] ).sum_range(0,1)\n  end\n\n  def test_wa_case\n    num_array = NumArray.new([0,9,5,7,3])\n    assert_equal 3,   num_array.sum_range(4,4)\n    assert_equal 15,  num_array.sum_range(2,4)\n    assert_equal 7,   num_array.sum_range(3,3)\n    num_array.update(4,5)\n    num_array.update(1,7)\n    num_array.update(0,8)\n    assert_equal 12,  num_array.sum_range(1,2)\n    num_array.update(1,9)\n    assert_equal 5,   num_array.sum_range(4,4)\n    num_array.update(3,4)\n  end\nend\n```
['Ruby']