Skip to content

Instantly share code, notes, and snippets.

@GaurangTandon
Last active October 23, 2020 17:38
Show Gist options
  • Save GaurangTandon/124f9917565aa87387f136ab29dd80dc to your computer and use it in GitHub Desktop.
Save GaurangTandon/124f9917565aa87387f136ab29dd80dc to your computer and use it in GitHub Desktop.

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

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

When to not use "lazy segtrees"

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

Further practice resources

Recommended practice questions:

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

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

@GaurangTandon
Copy link
Author

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!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment