Typical queries are range sum queries (calculating the sum of values) and range minimum queries (finding the minimum value). Furthermore, there are tree structures that are able to process queries and update array values in an efficient way. The first Structure is a binary indexed tree that supports sum and update queries in a given array and can be seen as a dynamic version of a prefix sum array. The Second structure is a segment tree and it is a more versatile structure that supports sum queries, minimum queries, and several other queries.
id| Data Structure| ——–|——————- RQDS18-BIT| Binary Indexed Tree RQDS18-ST| Segment Tree