test/datastructure/cul_sum_test.cr

View this file on GitHub
Last update: 2021-08-04 13:11:57+09:00
Problem: https://judge.yosupo.jp/problem/static_range_sum

Depends on

src/datastructure/cul_sum.cr

Code

# verification-helper: PROBLEM https://judge.yosupo.jp/problem/static_range_sum
require "../../src/datastructure/cul_sum"
_, q = read_line.split.map(&.to_i)
a = read_line.split.map(&.to_i64)
sum = CulSum.new(a)
q.times do
  l, r = read_line.split.map(&.to_i)
  puts sum[l...r]
end

# verification-helper: PROBLEM https://judge.yosupo.jp/problem/static_range_sum
# require "../../src/datastructure/cul_sum"
class CulSum(T)
  def self.build(a : Enumerable(T))
    result = [T.zero]
    a.each do |x|
      result << result[-1] + x
    end
    result
  end

  def initialize(a : Array(T))
    @n = a.size
    @s = Array(T).new(@n + 1, T.zero)
    @n.times do |i|
      @s[i + 1] = @s[i] + a[i]
    end
  end

  def initialize(@n : Int32, &f : Int32 -> T)
    @s = Array(T).new(@n + 1, T.zero)
    @n.times do |i|
      @s[i + 1] = @s[i] + yield(i)
    end
  end

  def initialize(a, &f)
    @n = a.size
    @s = Array(T).new(@n + 1, T.zero)
    @n.times do |i|
      @s[i + 1] = @s[i] + yield(a[i])
    end
  end

  def [](left : Int32, count : Int32) : T
    @s[left + count] - @s[left]
  end

  def [](range : Range) : T
    self[*Indexable.range_to_index_and_count(range, @n) || raise IndexError.new]
  end

  def to_a : Array(T)
    (0...@n).map { |i| self[i..i] }
  end
end

_, q = read_line.split.map(&.to_i)
a = read_line.split.map(&.to_i64)
sum = CulSum.new(a)
q.times do
  l, r = read_line.split.map(&.to_i)
  puts sum[l...r]
end