Week #05
	Pedro Ribeiro - DCC/FCUP

Main learning outcomes for this class

1. Cumulative Sums:
   • I know the concept of cumulative sums ("prefix sums")
   • I know the inclusion-exclusion principle and how to extend cumulative sums to more than one dimension
2. Fenwick Trees (Binary Indexed Trees, a.k.a. BITs):
   • I know the concept of a BIT, the way node store cumulative sums and its (simple) implementation
   • I know how to answer several types of queries related with sums, such as:
     • single updates, range queries [rangea(a,b) using bit(b)-bit(a-1)]
     • range updates, single queries [update(a,b,v) using update(a,v) and update(b+1,-v)]
     • range update, range queries [using two BITs]
   • I understand how to adapt to more dimensions, and in particular to the case of 2D (a BIT of BITs)
3. Maximum Subarray Problem:
   • I know the problem of determining maximum sum of a contiguous subsequence
   • I know Kadane's Algorithm to solve this problem in linear time

Study Material

Main references

• Video Lecture (my own video from the Topics in Advanced Algorithms course):
  • 1D Problems II (cumulative sums and fenwick trees) [YouTube]
• Cumulative sums
• Portuguese Olympiads Training (small translated section)
• Section 9.1 the Competitive Programmer's Handbook book
• BITs
• Binary Indexed Trees (Tutorial do TopCoder)
• Fenwick Tree (E-Maxx Algorithms)
• Various Usages of BITs
• Binary Indexed Trees with some Solved Examples
• Section 9.2 and 22.3 of the Competitive Programmer's Handbook book
• Fenwick, P. M. (1994). A new data structure for cumulative frequency tables. Software: Practice and Experience, 24(3), 327-336.
• Dima, M., & Ceterchi, R. (2015). Efficient range minimum queries using binary indexed trees. Olympiad in Informatics, 9(1), 39-44.
• Kadane's Algorithm
• Maximum Sub Array Problem (Wikipedia)
• Section 2.4 the Competitive Programmer's Handbook book

Initiation/Reinforcement Problems

• [UVA 10324] - Zeros and Ones (testing range query on a cumulative sums array)
• [UVA 836] - Largest Submatrix (testing cumulative sums for 2D - O(n⁴ still passes))
• [UVA 10755] - Garbage Heap (testing cumulative sums for 3D)
• [UVA 507] - Jill Rides Again (testing Kadane's Algorithm)

Pedro Ribeiro - DCC/FCUP | Last update: