## Query the sum of a submatrix

Maintain a matrix in a datastructure, allowing to update entries and to query the sum of a rectangular submatrix in time $O(\log(n)\log(m))$, where $n,m$ are the dimensions of the matrix.

See also all posts ordered by categories.

Maintain a matrix in a datastructure, allowing to update entries and to query the sum of a rectangular submatrix in time $O(\log(n)\log(m))$, where $n,m$ are the dimensions of the matrix.

Given a string $s$, determine the number of distinct substrings that it contains.

Given the a rewriting system of the form $f:\Sigma\rightarrow \Sigma^\star$, determine the limit of $f^i(a)$ for some given seed letter $a\in \Sigma$.

Given the grammar of a context free language and a string, decide if the string can be generated by the grammar.

Given directed graph with possibly negative edge weights, find a shortest path between two given vertices.

Given an undirected bipartite graph find a minimum cardinality vertex set which covers all edges in the sense that it contains at least one endpoint of each edge.

Given a string A (or array), and an integer k, find for every index i, the smallest index j (if it exists) such that {A[i],..,A[j-1]} consists of exact k distinct values.

Propose a data structure which permits to maintain a set of integers S, allowing to add elements and to remove the median. Both operations should work in logarithmic time.