class AcLibraryRb::Segtree

Segment Tree

Attributes

d[R]
leaf_size[R]
log[R]
n[R]
op[R]

Public Class Methods

new(a0, a1, a2 = nil, &block) click to toggle source

new(v, e){ |x, y| } new(v, op, e)

# File lib_lock/ac-library-rb/segtree.rb, line 8
def initialize(a0, a1, a2 = nil, &block)
  if a2.nil?
    @e, @op = a1, proc(&block)
    v = (a0.is_a?(Array) ? a0 : [@e] * a0)
  else
    @op, @e = a1, a2
    v = (a0.is_a?(Array) ? a0 : [@e] * a0)
  end

  @n = v.size
  @log = (@n - 1).bit_length
  @leaf_size = 1 << @log
  @d = Array.new(@leaf_size * 2, @e)
  v.each_with_index { |v_i, i| @d[@leaf_size + i] = v_i }
  (@leaf_size - 1).downto(1) { |i| update(i) }
end

Public Instance Methods

[](pos)
Alias for: get
[]=(q, x)
Alias for: set
all_prod() click to toggle source
# File lib_lock/ac-library-rb/segtree.rb, line 72
def all_prod
  @d[1]
end
get(pos) click to toggle source
# File lib_lock/ac-library-rb/segtree.rb, line 32
def get(pos)
  @d[@leaf_size + pos]
end
Also aliased as: []
max_right(l, &block) click to toggle source
# File lib_lock/ac-library-rb/segtree.rb, line 76
def max_right(l, &block)
  return @n if l == @n

  f = proc(&block)

  l += @leaf_size
  sm = @e
  loop do
    l /= 2 while l.even?
    unless f.call(@op.call(sm, @d[l]))
      while l < @leaf_size
        l *= 2
        if f.call(@op.call(sm, @d[l]))
          sm = @op.call(sm, @d[l])
          l += 1
        end
      end

      return l - @leaf_size
    end

    sm = @op.call(sm, @d[l])
    l += 1
    break if (l & -l) == l
  end

  @n
end
min_left(r, &block) click to toggle source
# File lib_lock/ac-library-rb/segtree.rb, line 105
def min_left(r, &block)
  return 0 if r == 0

  f = proc(&block)

  r += @leaf_size
  sm = @e
  loop do
    r -= 1
    r /= 2 while r > 1 && r.odd?
    unless f.call(@op.call(@d[r], sm))
      while r < @leaf_size
        r = r * 2 + 1
        if f.call(@op.call(@d[r], sm))
          sm = @op.call(@d[r], sm)
          r -= 1
        end
      end

      return r + 1 - @leaf_size
    end

    sm = @op.call(@d[r], sm)
    break if (r & -r) == r
  end

  0
end
prod(l, r = nil) click to toggle source
# File lib_lock/ac-library-rb/segtree.rb, line 37
def prod(l, r = nil)
  if r.nil? # if 1st argument l is Range
    if r = l.end
      r += @n if r < 0
      r += 1 unless l.exclude_end?
    else
      r = @n
    end
    l = l.begin
    l += @n if l < 0
  end

  return @e if l == r

  sml = @e
  smr = @e
  l += @leaf_size
  r += @leaf_size

  while l < r
    if l[0] == 1
      sml = @op.call(sml, @d[l])
      l += 1
    end
    if r[0] == 1
      r -= 1
      smr = @op.call(@d[r], smr)
    end
    l /= 2
    r /= 2
  end

  @op.call(sml, smr)
end
set(q, x) click to toggle source
# File lib_lock/ac-library-rb/segtree.rb, line 25
def set(q, x)
  q += @leaf_size
  @d[q] = x
  1.upto(@log) { |i| update(q >> i) }
end
Also aliased as: []=
update(k) click to toggle source
# File lib_lock/ac-library-rb/segtree.rb, line 134
def update(k)
  @d[k] = @op.call(@d[2 * k], @d[2 * k + 1])
end