KEMBAR78
Lazy Segment Trees - TLE 4 | PDF | Algorithms And Data Structures | Computer Programming
Scribd
Upload
10 views17 pages

Lazy Segment Trees - TLE 4

The document discusses the implementation of lazy segment trees for efficient range updates and queries on arrays. It outlines the time complexities for updates and queries, which are both O(logN), and highlights the use cases for adding values, returning sums, and other operations on specified ranges. Additionally, it notes the increased complexity and space requirements associated with lazy segment trees compared to standard segment trees.

Uploaded by

gaurav.anand.80926
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
10 views17 pages

Lazy Segment Trees - TLE 4

The document discusses the implementation of lazy segment trees for efficient range updates and queries on arrays. It outlines the time complexities for updates and queries, which are both O(logN), and highlights the use cases for adding values, returning sums, and other operations on specified ranges. Additionally, it notes the increased complexity and space requirements associated with lazy segment trees compared to standard segment trees.

Uploaded by

gaurav.anand.80926
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 17

Point updates

Range Queries I

Segment Trees Range pulsio

O(n)
(Lazy Propagation) n

=
0
(logn)
B wild, Update f
Query -
-

-
⑧(loga)
-
-
update value inden"pos"=
at
n
2

Range sum- (0,0) Zai-


i -11

ollogn)
-
time

① - -
update
all the values from 1 to s

by adding as D
to

all of them atign)


Range sum ->
, Add 5 to all indias

dsdon in
ranga (5,01

dbbdodo
-
-

12 1223 I
At i
12
our getdog
34

I O

And
000

old (14)
to
+ 10
to -

v
Query

E
aucies
Range
Completeoverlap (
① [I]
Node

o(logu) Return value


-
-

② Disjont [] [ I
Return Dafaut Valu

③ Partial overlap [[] I

%/b c c)
Range Update

① Compute overlop [[]]


Add 5 to

Yo ⑱
all nodes
in give range

date deg
② Disjoint [][]
return
just

③ Partial overlap (1])


d
(44)
** re
I

No
18
Ranga update
using lazy segment
Tree

·(gr)
-

Range query - 0(
-
logn)
build

update()
check if there are
any
*

qu pending changes in
lazy
segment He
>
=>
%co
d dobods 3

update(3,bs
[I 2 (0) O
Range
↑ M Range update (3,4,5
J
5
Range query (M)
is
·
Range
(3,7)
update

+ E
⑯ .s
-

Range update

do
(114)-> 10
-

Range query
(2,3)
- o
Use Case

● Perform the following 2 queries on an array:


○ 1 L R X -> Add X to all elements from L to R v
○ 2 L R -> Return the sum of all elements from L to R

● Perform the following 2 queries on an array:


○ 1 L R X -> Add X to all elements from L to R
○ 2 L R -> Return the min of all elements from L to R y-
● Perform the following 2 queries on an array:
○ 1 L R X -> Make all elements from L to R = X
3y
○ 2 L R -> Return the xor of all elements from L to R
-
-
- -
-
. 1

dd!
-

↓
2 3
-

- 55

lazy (2x index) +=


192y/inden)

lang in)=
lazy (indent
.. 9
.
8

e
X
③
Add 15,63 -

5
Lazy Segment Tree
● Range Updates are similar to Range Queries
● Same number of recursive calls for query as that for update
● Time Complexity for each update: O(logN)
● Time Complexity for each query: O(logN)
● Extra O(N) space for storing an additional tree
● Slower than normal segment tree
● Harder to code (Use Generic Segment Tree Code)
● Nothing fancy if you understand it properly - Super intuitive

You might also like