Static and dynamic data structures

In computer science, a static data structure is a data structure created for an input data set which is not supposed to change within the scope of the problem. When a single element is to be added or deleted, the update of a static data structure incurs significant costs, often comparable with the construction of the data structure from scratch. In real applications, dynamic data structures are used, which allow for efficient updates when data elements are inserted or deleted.

There exist methods, called dynamization, to convert static data structures into dynamic ones.

et inclusion query

A sorted array is an example of a static data structure which can be used to efficiently answer queries whether a given number belongs to a certain set of numbers: binary search answers such queries in O(log N) time, where N is the size of the array. But if one wants to add an element into a sorted array, O(N) time may be required in the worst case to update the data structure (e.g., when an insertion into the head of the array is required).

A balanced binary tree is a dynamic data structure for this type of query: not only it answers the inclusion queries in logarithmic time, insertions and deletions can be done in logarithmic time as well.