lazy-segtree-meet

# 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](https://codeforces.com/contest/145/problem/E)
- [A Simple Task](https://codeforces.com/contest/558/problem/E)

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

# When to not use "lazy segtrees"

- [Child And Sequence](https://codeforces.com/contest/438/problem/D)

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

# Further practice resources

- [CF blog](https://codeforces.com/blog/entry/22616)
- [CF Edu Part 2 Practice](https://codeforces.com/edu/course/2/lesson/5)

## Recommended practice questions:

1. Adding an AP to a update range [link](https://codeforces.com/edu/course/2/lesson/5/4/practice/contest/280801/problem/B)
2. Weighted queries [link](https://codeforces.com/edu/course/2/lesson/5/4/practice/contest/280801/problem/D)
3. Segment min/max [link](https://codeforces.com/edu/course/2/lesson/5/4/practice/contest/280801/problem/E)