This post is just for revising range queries. Have highlighted the topics and problems. Might write solutions (my approach) for these problems as well for future reference.

to do : create collapsible for solutions + also to put the same in DP post

Table of Contents (segment tree)

Link: cp-algorithms - Segment tree

  • Simplest form of a Segment Tree ✔️
    • Structure of the Segment Tree ✔️
    • Construction ✔️
    • Sum queries ✔️
    • Update queries ✔️
    • Implementation ✔️
    • Memory efficient implementation ✔️
  • Advanced versions of Segment Trees
    • More complex queries ✔️
    • Saving the entire subarrays in each vertex ✔️
    • Range updates (Lazy Propagation) ✔️
    • Generalization to higher dimensions 📝
    • Preserving the history of its values (Persistent Segment Tree)
    • Implicit segment tree

Table of Contents (fenwick tree or BIT)

Link: cp-algorithms - Fenwick tree

  • Description
    • Overview ✔️
    • Definition of g(i) ✔️
  • Implementation
    • Finding sum in one-dimensional array ✔️
    • Finding minimum of [0,r] in one-dimensional array ✔️
    • Finding sum in two-dimensional array ✔️
    • One-based indexing approach ✔️
  • Range operations
    1. Point Update and Range Query ✔️
    2. Range Update and Point Query 📝
    3. Range Updates and Range Queries 📝
CSES.fi problemSet (Range Queries)
  1. Range Sum Queries I ✔️
  2. Range Sum Queries I ✔️
  3. Range Minimum Queries I ✔️
  4. Range Sum Queries II ✔️
  5. Range Minimum Queries II ✔️
  6. Range Xor Queries ✔️
  7. Range Update Queries ✔️
  8. Forest Queries ✔️
  9. Hotel Queries ✔️
  10. List Removals ✔️
  11. Salary Queries
  12. Subarray Sum Queries
  13. Distinct Values Queries
  14. Forest Queries II
  15. Range Updates and Sums
  16. Polynomial Queries
  17. Range Queries and Copies