Many algorithmic problems stated in terms of fixed input data (called static problems in this context and solved by static algorithms) have meaningful dynamic versions.
If both additions and deletions are allowed, the algorithm is sometimes called fully dynamic.
A well-known solution for this problem is using a self-balancing binary search tree.
It takes space O(N), may be initially constructed in time O(N log N) and provides insertion, deletion and query times in O(log N).
Given a graph, maintain its parameters, such as connectivity, maximal degree, shortest paths, etc., when insertion and deletion of its edges are allowed.