Tờ Mờ Sáng học Thuật toán và Lập trình thi đấu

Range Queries

Tổng hợp danh sách những tài liệu hay và bổ ích về Thuật toán và Lập trình thi đấu

Người tổng hợp: Trần Minh Sáng

Series video "Lên trình Thuật toán - Lập trình thi đấu":

Cài đặt extension Random Algorithm Topics trên Google Chrome để học ngẫu nhiên một chủ đề trong danh sách mỗi khi mở 1 tab mới trên trình duyệt

Install on Google Chrome

Nội dung chính của phần "Range Queries"

• Queries on Static Arrays
  • Sum Queries
  • Minimum Queries
• Tree Structures
  • Binary Indexed Trees
  • Segment Trees
  • Additional Techniques

Queries on Static Arrays

Sum Queries

• Bài viết tiếng Anh:
  • Mục 9.1.1 Sum Queries trong cuốn Guide to Competitive Programming
  • Range sum queries without updates
  • CSES Range Queries solutions - Codeforces Blog
• Video tiếng Anh:
  • Range Sum Query 2D - Immutable - Leetcode 304 - Python
  • Range Sum Query Immutable - Leetcode 303 - Python
  • Prefix Sum Array and Range Sum Queries
  • Range Sum Query 2D

Minimum Queries

• Bài viết tiếng Việt:
  • Bài toán RMQ và bài toán LCA - Binary Lifting - VNOI Wiki
  • Bài toán RMQ và bài toán LCA - VNOI Wiki
  • Range Minimum Query (RMQ) - Sparse Table - VNOI Wiki
  • Bảng thưa (Sparse Table) - Cấu trúc dữ liệu rất mạnh để giải quyết bài toán Range Minimum Queries (RMQ)
  • Range Minimum Query (RMQ) – Sparse Table
• Video tiếng Việt:
  • SparseTable (RMQ) - YugiHacker
  • Sparse Table
• Bài viết tiếng Anh:
  • Mục 9.1.2 Minimum Queries trong cuốn Guide to Competitive Programming
  • Range Minimum Query and Lowest Common Ancestor - TopCoder
  • Range minimum query - Wikipedia
  • Range Minimum Query - cp-algorithms
  • Solve RMQ (Range Minimum Query) by finding LCA (Lowest Common Ancestor) - cp-algorithms
  • Range Minimum Query (Square Root Decomposition and Sparse Table) - GeeksforGeeks
  • Range Minimum Queries - Đại học Standford
• Video tiếng Anh:
  • Sparse Table & RMQ (Range Minimum Query)
  • Sparse Table Algorithm Range Minimum Query
  • Segment Tree Range Minimum Query
  • Sparse Table Data Structure
  • Range minimum query | 3 methods
  • AlgorithmsThread 2: RMQ Tricks

Tree Structures

Binary Indexed Trees

• Bài viết tiếng Việt:
  • Cây chỉ số nhị phân (Binary Indexed Tree) - VNOI Wiki
  • Cây chỉ số nhị phân 2 chiều (BIT 2 chiều) - VNOI Wiki
  • Cấu trúc dữ liệu BIT – Binary Indexed Tree (Fenwick Tree)
  • Fenwick Tree - HowKteam
• Video tiếng Việt:
  • BIT (Fenwick Tree) - Cây chỉ số nhị phân [C++] - YugiHacker
  • Fenwick Tree - cây nhị phân nhưng không hề nhị phân - GSPVHCUTE
  • Binary Indexed Tree
• Bài viết tiếng Anh:
  • Mục 9.2.1 Binary Indexed Trees trong cuốn Guide to Competitive Programming
  • Fenwick Tree - cp-algorithms
  • Binary Indexed Tree or Fenwick Tree - HackerEarth
  • Fenwick tree - Wikipedia
  • Binary Indexed Tree or Fenwick Tree - GeeksforGeeks
  • Fenwick Tree (Binary Indexed Tree) for Competitive Programming - GeeksforGeeks
  • Binary Indexed Trees - TopCoder
  • Understanding Fenwick Trees / Binary Indexed Trees - Codeforces Blog
  • VisuAlgo
• Video tiếng Anh:
  • Fenwick Tree or Binary Indexed Tree
  • Fenwick Tree (Binary Index Tree) - Quick Tutorial and Source Code Explanation
  • Fenwick Tree range queries
  • Binary Indexed Tree or Fenwick Tree | Construction and Operations | GeeksforGeeks
  • Tutorial: Binary Indexed Tree (Fenwick Tree)

Segment Trees

• Bài viết tiếng Việt:
  • Cây Phân Đoạn (cơ bản) - VNOI Wiki
  • Tất tần tật về Cây Phân Đoạn (Segment Tree) - VNOI Wiki
  • Cài đặt cây phân đoạn hiệu quả (Efficient and easy segment trees) - VNOI Wiki
  • Cây Đoạn (Segment Tree) là gì?
  • Cây phân đoạn (Segment tree)
  • Cây phân đoạn nâng cao (Segment trees advanced)
  • Segment Tree
• Video tiếng Việt:
  • Segment Tree (Cây phân đoạn) [C++] [2021] - YugiHacker
  • Segment Tree - Cây phân đoạn [C++] [2023], Đoạn con có tổng lớn nhất, Tìm nhị phân trên segment tree
  • Segment Tree - Lazy propagation [C++] [2023], Cây phân đoạn, cập nhật lười, cập nhật bậc thang
  • Cài Đặt Segment Tree (Cây phân đoạn) trên C++
• Bài viết tiếng Anh:
  • Mục 9.2.2 Segment Trees trong cuốn Guide to Competitive Programming
  • Segment Tree - cp-algorithms
  • Segment tree
  • Efficient and easy segment trees - Codeforces Blog
  • Segment tree - Wikipedia
  • Segment Tree - GeeksforGeeks
  • Segment Trees - HackerEarth
  • VisuAlgo
• Video tiếng Anh:
  • Segment Tree Range Minimum Query
  • Lazy Propagation Segment Tree
  • Segment tree
  • Segment Tree: CodeNCode
  • Segment Tree Concepts and Questions
  • Segment Tree - Level 3
  • Segment Trees - The Best Introduction in 10 mins
  • Segment Tree: Build and Query | Live Coding
  • Lazy Propagation in Segment Tree | Point and Range Updates | Live Coding

Additional Techniques

• Bài viết tiếng Anh:
  • Mục 9.2.3 Additional Techniques trong cuốn Guide to Competitive Programming