lazysegtreemeet.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

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

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

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.

Actual problems

• Lucky Queries
• A Simple Task

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

When to not use "lazy segtrees"

• Child And Sequence

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

Can you set the extension to .md, so it'll render the markdown?

Ah, of course. The whole time I was wondering why didn't it render and I didn't notice the file extension at all :facepalm:. Thanks!