Questions for Lazy Segtree Meet

questions.md

Basic segtree (prerequisite)

Given n values a[1], ..., a[n], you entertain two types of queries:

• point update: add x to the i-th value
• range query: query minimum value of a[i] in the range l, r

Around 5 mins max. LIVE CODE.

Simple lazy segtree

Given n values a[1], ..., a[n], you entertain two types of queries:

• range update: add x to all values of a[i] in the range l, r
• range query: query minimum value of a[i] in the range l, r

Around 30mins/as long as everyone understands. LIVE CODE.

Typical lazy segtree

Given n values a[1], ..., a[n], you entertain three types of queries:

• range update: add x to all values of a[i] in the range l, r
• range set: set all values of a[i] in the range l, r to the value x
• range query: query minimum value of a[i] in the range l, r

Around 10mins/as long as everyone understands. LIVE CODE.

Slight query variation

Given n values a[1], ..., a[n], you entertain three types of queries:

• range update: add x to all values of a[i] in the range l, r
• range sum: query sum of values of a[i] in the range l, r
• range max: query max of all values of a[i] in the range l, r

Discuss orally for 5-10mins.

Actual problems

• Lucky Queries
• A Simple Task

Will discuss ideas for both and CODE one of them (if time permits)

Around 15mins each/as long as everyone understands.

When to not use "lazy segtrees"

• Child And Sequence

Around 15mins/as long as everyone understands.

More such questions: CF SUM AND REPLACE, SPOJ GSS4.

Further practice resources

• CF blog
• CF Edu Part 2 Practice

Recommended practice questions:

1. Adding an AP to a update range link
2. Weighted queries link
3. Segment min/max link