Class: LazySegtree

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

Overview

Segment tree with Lazy propagation

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(v, a1, a2, a3 = nil, a4 = nil, a5 = nil, &op_block) ⇒ LazySegtree

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



9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
# File 'lib/lazy_segtree.rb', line 9

def initialize(v, a1, a2, a3 = nil, a4 = nil, a5 = nil, &op_block)
  if a1.is_a?(Proc)
    @op, @e, @mapping, @composition, @id = a1, a2, a3, a4, a5
  else
    @e, @id, @op, @mapping, @composition = a1, a2, a3, a4, a5
    @op ||= op_block
  end
  v = Array.new(v, @e) if v.is_a?(Integer)

  @n  = v.size

  @log  = (@n - 1).bit_length
  @size = 1 << @log
  @d    = Array.new(2 * @size, e)
  @lz   = Array.new(@size, id)

  @n.times { |i| @d[@size + i] = v[i] }
  (@size - 1).downto(1) { |i| update(i) }
end

Instance Attribute Details

#composition ⇒ Object

Returns the value of attribute composition.



4
5
6
 
# File 'lib/lazy_segtree.rb', line 4

def composition
  @composition
end

#d ⇒ Object (readonly)

Returns the value of attribute d.



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

def d
  @d
end

#e ⇒ Object (readonly)

Returns the value of attribute e.



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

def e
  @e
end

#id ⇒ Object (readonly)

Returns the value of attribute id.



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

def id
  @id
end

#lz ⇒ Object (readonly)

Returns the value of attribute lz.



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

def lz
  @lz
end

#mapping ⇒ Object

Returns the value of attribute mapping.



4
5
6
 
# File 'lib/lazy_segtree.rb', line 4

def mapping
  @mapping
end

#op ⇒ Object

Returns the value of attribute op.



4
5
6
 
# File 'lib/lazy_segtree.rb', line 4

def op
  @op
end

Instance Method Details

#all_apply(k, f) ⇒ Object 



206
207
208
209
 
# File 'lib/lazy_segtree.rb', line 206

def all_apply(k, f)
  @d[k]  = @mapping.call(f, @d[k])
  @lz[k] = @composition.call(f, @lz[k]) if k < @size
end

#all_prod ⇒ Object 



92
93
94
 
# File 'lib/lazy_segtree.rb', line 92

def all_prod
  @d[1]
end

#apply(pos, f, fr = nil) ⇒ Object

apply(pos, f) apply(l, r, f) -> range_apply(l, r, f) apply(l…r, f) -> range_apply(l, r, f) … [Experimental]



99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
 
# File 'lib/lazy_segtree.rb', line 99

def apply(pos, f, fr = nil)
  if fr
    return range_apply(pos, f, fr)
  elsif pos.is_a?(Range)
    l = pos.begin
    l += @n if l < 0
    if r = pos.end
      r += @n if r < 0
      r += 1 unless pos.exclude_end?
    else
      r = @n
    end
    return range_apply(l, r, f)
  end

  pos += @size
  @log.downto(1) { |i| push(pos >> i) }
  @d[pos] = @mapping.call(f, @d[pos])
  1.upto(@log) { |i| update(pos >> i) }
end

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



45
46
47
48
49
 
# File 'lib/lazy_segtree.rb', line 45

def get(pos)
  pos += @size
  @log.downto(1) { |i| push(pos >> i) }
  @d[pos]
end

#max_right(l, &g) ⇒ Object 



148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
 
# File 'lib/lazy_segtree.rb', line 148

def max_right(l, &g)
  return @n if l == @n

  l += @size
  @log.downto(1) { |i| push(l >> i) }
  sm = @e

  loop do
    l >>= 1 while l.even?
    unless g.call(@op.call(sm, @d[l]))
      while l < @size
        push(l)
        l <<= 1
        if g.call(@op.call(sm, @d[l]))
          sm = @op.call(sm, @d[l])
          l += 1
        end
      end
      return l - @size
    end
    sm = @op.call(sm, @d[l])
    l += 1
    break if l & -l == l
  end
  @n
end

#min_left(r, &g) ⇒ Object 



175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
 
# File 'lib/lazy_segtree.rb', line 175

def min_left(r, &g)
  return 0 if r == 0

  r += @size
  @log.downto(1) { |i| push((r - 1) >> i) }
  sm = @e

  loop do
    r -= 1
    r /= 2 while r > 1 && r.odd?
    unless g.call(@op.call(@d[r], sm))
      while r < @size
        push(r)
        r = r * 2 + 1
        if g.call(@op.call(@d[r], sm))
          sm = @op.call(@d[r], sm)
          r -= 1
        end
      end
      return r + 1 - @size
    end
    sm = @op.call(@d[r], sm)
    break if (r & -r) == r
  end
  0
end

#prod(l, r = nil) ⇒ Object 



52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
 
# File 'lib/lazy_segtree.rb', line 52

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

  l += @size
  r += @size

  @log.downto(1) do |i|
    push(l >> i) if (l >> i) << i != l
    push(r >> i) if (r >> i) << i != r
  end

  sml = @e
  smr = @e
  while l < r
    if l.odd?
      sml = @op.call(sml, @d[l])
      l += 1
    end
    if r.odd?
      r -= 1
      smr = @op.call(@d[r], smr)
    end
    l >>= 1
    r >>= 1
  end

  @op.call(sml, smr)
end

#push(k) ⇒ Object 



211
212
213
214
215
 
# File 'lib/lazy_segtree.rb', line 211

def push(k)
  all_apply(2 * k,     @lz[k])
  all_apply(2 * k + 1, @lz[k])
  @lz[k] = @id
end

#range_apply(l, r, f) ⇒ Object 



120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
 
# File 'lib/lazy_segtree.rb', line 120

def range_apply(l, r, f)
  return if l == r

  l += @size
  r += @size

  @log.downto(1) do |i|
    push(l >> i) if (l >> i) << i != l
    push((r - 1) >> i) if (r >> i) << i != r
  end

  l2 = l
  r2 = r
  while l < r
    (all_apply(l, f); l += 1) if l.odd?
    (r -= 1; all_apply(r, f)) if r.odd?
    l >>= 1
    r >>= 1
  end
  l = l2
  r = r2

  1.upto(@log) do |i|
    update(l >> i)       if (l >> i) << i != l
    update((r - 1) >> i) if (r >> i) << i != r
  end
end

#set(pos, x) ⇒ Object Also known as: []= 



37
38
39
40
41
42
 
# File 'lib/lazy_segtree.rb', line 37

def set(pos, x)
  pos += @size
  @log.downto(1) { |i| push(pos >> i) }
  @d[pos] = x
  1.upto(@log) { |i| update(pos >> i) }
end

#set_composition(&composition) ⇒ Object 



33
34
35
 
# File 'lib/lazy_segtree.rb', line 33

def set_composition(&composition)
  @composition = composition
end

#set_mapping(&mapping) ⇒ Object 



29
30
31
 
# File 'lib/lazy_segtree.rb', line 29

def set_mapping(&mapping)
  @mapping = mapping
end

#update(k) ⇒ Object 



202
203
204
 
# File 'lib/lazy_segtree.rb', line 202

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