# Ruby Solution

• As I met 307. Range Sum Query - Mutable first, I’ve got some “advanced” thoughts on RMQ after passing it. So that’s why I was stuck on this problem, Einstellung.

At first, I made a SparseTable, which is O(NlogN) on preprocessing and O(logN) on query. Time Limit Exceed.

``````# This is a sparse table calculating sum of data[i..j]
class SparseTable

def initialize(data)
@data = data.empty? ? [0] : data
@value = Array.new(@data.count) { Array.new(@data.count) {0} }

build
end

def query(i, j)
recur_query(i, j)
end

private

# setup value, which value[i][j] represents sum of data[i..i+2**j-1]
def build
data.each_index do |i|
value[i][0] = data[i]
end

j = 1
loop do
break if 2**j > data.count

data.each_index do |i|
left  = value[i][j-1]
right = i+2**(j-1) > data.count - 1 ? 0 : value[i+2**(j-1)][j-1]

value[i][j] = left + right
end

j += 1
end
end

def recur_query(i, j)
return 0 if i > j

j = data.count - 1 if j > data.count - 1

bin = (j-i+1).to_s(2)
sum = 0
pos = i

bin.chars.reverse.each_with_index do |ch, k|
next if ch == '0'

sum += value[pos][k]
pos += 2**k
end

sum
end
end
``````

Then, I made a bottom-up DP version, which is O(N^2) on preprocessing and O(1) on query. As I’m writing Ruby, this is still a TLE.

``````# DP version with preprocessing O(N^2) and query O(1)
class NumArray

def initialize(nums)
@nums = nums
@value = Array.new(nums.count) { Array.new(nums.count) {0} }

nums.each_index do |i|
@value[i][i] = nums[i]
end

gap = 1
loop do
break if gap > nums.count - 1

nums.each_index do |i|
break if i+gap > nums.count - 1

@value[i][i+gap] = @value[i][i+gap-1] + nums[i+gap]
end

gap += 1
end
end

def sum_range(i, j)
j = @nums.count - 1 if j > @nums.count - 1

value[i][j]
end
end
``````

After these stupid TLE attempts, I noticed that this is an “easy” problem and I know this should be passed by O(N) (or O(NlogN)) on preprocessing and O(1) on query. So finally, pass it by

``````class NumArray

def initialize(nums)
@nums = nums
@sum  = Array.new( @nums.count ) {0}
preprocess
end

def sum_range(i, j)
sum[j] - sum[i] + nums[i]
end

private

def preprocess
sum[0] = nums[0]

nums.each_index do |i|
next if i == 0

sum[i] = sum[i-1] + nums[i]
end
end
end
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.