とある集計プログラムを速くできなかったorz

某所の問題

某施設の時間あたり利用者数aがn個与えられるので
指定された範囲（s個目〜t個目）の合計利用者数をm回算出するだけ。
利用者数aは0〜20000
nは1〜100000
mも1〜100000

データは以下が標準入力で与えられる

n m
a1
a2
...
an
s1 t1
s2 t2
...
sm tm

以下がコード。二分木作るより配列をrangeで抜いてsumったほうが(@an[(s-1)..(t-1)].inject(&:+))速いんだけどなんで。

# ! /usr/bin/env ruby

class Node
  attr_accessor :left, :right, :begin, :end, :sum
  def initialize(i,j,x)
    @begin=i
    @end=j
    @sum=x
  end
end

class Count
  def initialize(n,m)
    @n = n
    @m = m
    @an = []

    @summarized = false
  end

  def add(x)
    @an << x
  end

  # ナイーブ実装
  def psum(s,t)
    @an[(s-1)..(t-1)].inject(&:+)
  end

  # 二分探索
  def sum(s,t)
    s-=1
    t-=1
    pre_sum unless @summarized
    # "%d %d" % [s,t]
    return @an[s] if s==t
    return r_find(s,t)
  end

  private 

  def r_find(s,t)
    #p "%d %d" % [s,t]
    if @memo.begin == s && @memo.end == t
      return @memo.sum
    elsif s == t
      return @an[s]
    else
      med = (s + t) / 2
      return r_find(s, med) + r_find(med+1, t)
    end
  end

  # 二分木作る
  def pre_sum
    @summarized = true
    pre_sum_1(@an)
  end

  def pre_sum_1(a)
    i = 0
    tmp = []
    a.each_slice(2) do |x|
      if x.size > 1
        tmp << Node.new(i,i+1,x[0]+x[1])
      else
        tmp << Node.new(i,i,x[0])
      end
      i += 2
    end
    @memo = r_pre_sum(tmp)
  end

  def r_pre_sum(x)
    if x.size > 1
      tmp = []
      x.each_slice(2) do |x|
        if x.size > 1
          n = Node.new(x[0].begin,x[1].end,x[0].sum+x[1].sum)
          n.left = x[0]
          n.right = x[1]
        else
          n = x[0]
        end
        tmp << n
      end
      return r_pre_sum(tmp)
    else
      x[0]
    end
  end

end


if $0 == __FILE__

  def i_gets
    gets.split.map(&:to_i)
  end

  n, m = i_gets

  counter = Count.new(n,m)

  n.times do
    counter.add(i_gets[0])
  end

  m.times do
    puts counter.sum(*i_gets)
  end
end

__END__
5 3
6
0
1
3
12
1 3
4 5
2 2

とりあえず俺は課題の変数名とコードの変数名を合わせたらいいと思った。