Submission #66713738

---

Source Code Expand

class RsqSegmentTree
  attr_reader :size, :dat

  def initialize(n)
    @leafs = 1
    @leafs *= 2 while @leafs < n
    @dat = Array.new(size, 0)
  end

  def size = 2 * @leafs - 1

  def update(pos, x)
    index = pos + (size / 2)
    @dat[index] = x
    while index > 0
      index = parent(index)
      left_child = left_child(index)
      right_child = right_child(index)
      @dat[index] = [@dat[left_child], @dat[right_child]].sum
    end
  end

  # [l, r)
  # [a, b)
  def query(l, r, a=0, b=@leafs, index=0)
    return @dat[index] if (l <= a && b <= r)
    return 0 if (b <= l || r <= a)
    mid = (a + b) / 2
    left_ret = query(l, r, a, mid, left_child(index))
    right_ret = query(l, r, mid, b, right_child(index))
    [left_ret, right_ret].sum
  end

  private

  def parent(child) = (child - 1) / 2
  def left_child(parent) = 2 * parent + 1
  def right_child(parent) = 2 * parent + 2
end

n, q = gets.split.map(&:to_i)
segment_tree = RsqSegmentTree.new(n)
q.times do
  case gets.split.map(&:to_i)
  in [1, pos, x]
    segment_tree.update(pos - 1, x)
  in [2, l, r]
    puts segment_tree.query(l - 1, r - 1)
  end
end

Submission Info

Judge Result