Week #04 | |

Pedro Ribeiro - DCC/FCUP |

**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**

- I know the concept of
**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)

- I know the
**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

- I know the problem of determining

**Video Lecture**(my own video from the Topics in Advanced Algorithms course):**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

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

Pedro Ribeiro - DCC/FCUP |
**Último update:**