bitree.rb

class BITree
  def initialize(size)
    @level = size.bit_length
    @level -= 1 if (1 << (@level - 1)) == size
    @offset = 1 << (@level - 1)
    @size = 1 << @level
    @arr = [0] * @size
  end

  def add(i, n)
    i += @offset * 2
    while i >= 1
      f = i & 1
      i >>= 1
      @arr[i] += n if f == 0
    end
    @arr[0] += n
  end

  def sum(i)
    return @arr[0] if i >= @size
    offset = 1
    sum = 0
    l = @level
    while l > 0
      return sum if i & ((1 << l) - 1) == 0
      if i[l - 1] == 1
        v = @arr[offset + (i >> l)]
        sum += v
      end
      offset <<= 1
      l -= 1
    end
    sum
  end
end

# test
bt = BITree.new 1024
MOD = 10**9 + 7
a = 17
1024.times do |i|
  bt.add i, a.pow(i, MOD)
end
(0..1024).each do |i|
  expected = (a.pow(i, MOD) - 1) * (a - 1).pow(MOD - 2, MOD) % MOD
  raise unless bt.sum(i) % MOD == expected
end

extgcd.rb

def extgcd(a, b)
  return [0, 1, b] if a == 0
  return [1, 0, a] if b == 0
  i, j, gcd = solve a % b, b % a
  [i - b / a * j, j - a / b * i, gcd]
end

a, b, c = 42, 15, 900
x, y, gcd = extgcd a, b
raise unless c % gcd == 0
n = c / gcd
an = x * n - b * (x * n / b)
bn = y * n + a * (x * n / b)
an * a + bn * b == c # with minimum an>=0 and maximum bn

pq.rb

class PQ
  def initialize
    clear
  end

  def clear
    @heap = [nil]
  end

  def enq(value)
    @heap << value
    up_heap(@heap.size - 1)
    self
  end

  def up_heap(i)
    value = @heap[i]
    while i > 1
      j = i / 2
      parent = @heap[j]
      break if parent <= value
      @heap[i] = parent
      i = j
    end
    @heap[i] = value
  end

  def down_heap(i)
    value = @heap[i]
    while true
      j = 2 * i
      k = j + 1
      break unless @heap[j]
      l = !@heap[k] || @heap[j] < @heap[k] ? j : k
      cvalue = @heap[l]
      break if cvalue >= value
      @heap[i] = cvalue
      i = l
    end
    @heap[i] = value
  end

  def top
    @heap[1]
  end

  def deq
    value = @heap[1]
    if @heap.size <= 2
      @heap = [nil]
    else
      @heap[1] = @heap.pop
      down_heap 1
    end
    value
  end

  def size
    @heap.size - 1
  end

  alias first top
  alias << enq
end

# TEST
pq = PQ.new
1000.times { pq << rand(500) << rand(500); pq.deq }
values = pq.size.times.map { pq.deq }
p values.sort == values
100.times { pq << (_1 + 1) * 37 % 100 }
100.times { pq << (_1 + 1) * 19 % 100 }
p 200.times.map { pq.deq } == 200.times.to_a.map { _1 / 2 }

pq2.rb

class PQ2
  def initialize
    clear
  end

  def clear
    @heap = [nil]
  end

  def enq(priority, value)
    index = @heap.size
    node = [priority, value, index]
    @heap << node
    up_heap index
    node
  end

  def up_heap(i)
    node = @heap[i]
    while i > 1
      j = i / 2
      parent = @heap[j]
      break if parent[0] <= node[0]
      @heap[i] = parent
      parent[2] = i
      i = j
    end
    @heap[i] = node
    node[2] = i
  end

  def down_heap(i)
    node = @heap[i]
    while true
      j = 2 * i
      k = j + 1
      break unless @heap[j]
      l = !@heap[k] || @heap[j][0] < @heap[k][0] ? j : k
      cnode = @heap[l]
      break if cnode[0] >= node[0]
      @heap[i] = cnode
      cnode[2] = i
      i = l
    end
    @heap[i] = node
    node[2] = i
  end

  def update(index, priority)
    node = @heap[index]
    prev = node[0]
    node[0] = priority
    if prev < priority
      down_heap index
    else
      up_heap index
    end
  end

  def top
    @heap[1]
  end

  def deq
    node = @heap[1]
    return unless node
    if @heap.size <= 2
      @heap = [nil]
    else
      @heap[1] = @heap.pop
      down_heap 1
    end
    node.pop
    node
  end

  def size
    @heap.size - 1
  end

  alias first top
end

# TEST
pq = PQ2.new
nodes = 100.times.map do
  n = (_1 + 1) * 37 % 100
  pq.enq rand(100), n.to_s
end
nodes.shuffle.each { pq.update _3, _2.to_i }
p pq.size.times.map { pq.deq } == 100.times.map { [_1, _1.to_s] }
1000.times { pq.enq rand(500), nil; pq.enq rand(500), nil; pq.deq }
values = pq.size.times.map { pq.deq[0] }
p values.sort == values

union_find.rb

class UF
  def initialize(size)
    @arr = [-1] * size
  end
  def unite(a, b)
    ra = root a
    rb = root b
    return if ra == rb
    @arr[rb] += @arr[ra]
    @arr[ra] = rb
  end
  def root(a)
    return a if @arr[a] < 0
    @arr[a] = root @arr[a]
  end
  def roots
    (0...@arr.size).select { @arr[_1] < 0 }
  end
  def size(a)
    -@arr[root a]
  end
  def same?(a, b)
    root(a) == root(b)
  end
end

# test
uf = UF.new 1000
values = 1000.times.to_a
a = values.sample 200
b = (values - a).sample 300
c = (values - a - b).shuffle
[a, b, c].each do |group|
  (1...group.size).each do |i|
    uf.unite group[i], group[rand(i)]
  end
end
raise unless uf.roots.map {|r| uf.size(r) }.sort == [200, 300, 500]
raise unless [a, b, c].all? do |group|
  group.size.times.all? { uf.same? group.sample, group.sample }
end
raise if uf.same? a.sample, b.sample
raise if uf.same? b.sample, c.sample
raise if uf.same? c.sample, a.sample
raise unless [a, b, c].map { uf.size(_1.sample) } == [200, 300, 500]