Class: Segtree

Inherits:
Object
  • Object
show all
Defined in:
lib/segtree.rb

Overview

Segment Tree

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(a0, a1, a2 = nil, &block) ⇒ Segtree

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



7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
# File 'lib/segtree.rb', line 7

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

Instance Attribute Details

#d ⇒ Object (readonly)

Returns the value of attribute d.



3
4
5
 
# File 'lib/segtree.rb', line 3

def d
  @d
end

#leaf_size ⇒ Object (readonly)

Returns the value of attribute leaf_size.



3
4
5
 
# File 'lib/segtree.rb', line 3

def leaf_size
  @leaf_size
end

#log ⇒ Object (readonly)

Returns the value of attribute log.



3
4
5
 
# File 'lib/segtree.rb', line 3

def log
  @log
end

#n ⇒ Object (readonly)

Returns the value of attribute n.



3
4
5
 
# File 'lib/segtree.rb', line 3

def n
  @n
end

#op ⇒ Object (readonly)

Returns the value of attribute op.



3
4
5
 
# File 'lib/segtree.rb', line 3

def op
  @op
end

Instance Method Details

#all_prod ⇒ Object 



71
72
73
 
# File 'lib/segtree.rb', line 71

def all_prod
  @d[1]
end

#get(pos) ⇒ Object Also known as: [] 



31
32
33
 
# File 'lib/segtree.rb', line 31

def get(pos)
  @d[@leaf_size + pos]
end

#max_right(l, &block) ⇒ Object 



75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
 
# File 'lib/segtree.rb', line 75

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) ⇒ Object 



104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
 
# File 'lib/segtree.rb', line 104

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) ⇒ Object 



36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 
# File 'lib/segtree.rb', line 36

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) ⇒ Object Also known as: []= 



24
25
26
27
28
 
# File 'lib/segtree.rb', line 24

def set(q, x)
  q += @leaf_size
  @d[q] = x
  1.upto(@log) { |i| update(q >> i) }
end

#update(k) ⇒ Object 



133
134
135
 
# File 'lib/segtree.rb', line 133

def update(k)
  @d[k] = @op.call(@d[2 * k], @d[2 * k + 1])
end