Quadtree 2026-10-20
A tree in which each internal node has four children, commonly representing the four equal quadrants of a square region. For image compression, a uniform square can be stored as one leaf; a mixed square is split recursively. Large uniform regions therefore need few nodes.
Fenwick tree 2026-10-20
A Fenwick tree stores a changing array so that a point update and a prefix sum query each take time with storage. With indices starting at , the entry at stores the sum over the final block of length ending at . A query repeatedly removes that final block, while an update visits the blocks containing the changed position.
Monotone stack 2026-10-20
A stack whose stored values remain ordered by removing incompatible values before each insertion. In subarray-minimum counting, an entry can store a value and the number of suffixes for which it is currently minimal. Each item is pushed and popped at most once, giving linear total work for a full scan.
Trie Created 2026-10-20 Updated 2026-11-05
A trie stores strings in a rooted tree whose edges represent symbols; the path from the root spells a prefix. A separate terminal marker distinguishes a stored word from a prefix of another. Storing to, tea and ten shares the initial t, and tea with ten also shares te. Lookup follows one edge per symbol, taking time for a length- key when child selection is constant-time. Dense child arrays use more memory than sparse maps. A trie naturally supports prefix queries and longest-prefix matching.[ref]
Double-ended queue Created 2026-10-20 Updated 2026-11-05
A double-ended queue supports insertion and removal at both ends. It combines the access patterns of a stack and a queue without promising fast arbitrary indexing. For example, appending a,b at the right and then c at the left produces c,a,b; removing at the right returns b. A circular array or a doubly linked list can implement the abstraction, with different allocation and indexing costs. Python's deque provides approximately constant-time end operations, unlike repeatedly inserting at the start of an ordinary list.[ref]
Suffix automaton Created 2026-10-20 Updated 2026-11-05
A suffix automaton is a minimal partial deterministic finite automaton accepting the suffixes of a fixed string. Every path from its initial state spells a substring; marking every state accepting therefore recognizes all substrings, though that altered automaton need not be minimal for the larger language.
For a nonempty substring , let be the set of positions where an occurrence ends. End-position equivalence groups substrings with the same such set into one state. In ababa, b and ab both end at positions two and four, so they share a state. A character transition extends each represented occurrence; a suffix link leads to the class of the longest suffix outside the current class.[ref]
This represents many substrings with only linearly many states and transitions. The documented incremental construction creates a state for a newly appended character and, when needed, a clone separating incompatible continuation histories. With a fixed finite alphabet it takes time for a length- string. A membership query follows the proposed string's character transitions and fails at the first missing transition.[ref]
Treap 2026-10-20
A treap is a binary search tree ordered by keys and simultaneously a binary heap ordered by priorities. Independent random priorities give logarithmic expected search depth. An implicit treap uses subtree sizes to address sequence positions instead of storing explicit keys.
Associative array Created 2026-10-20 Updated 2026-10-31
A collection associating keys with values and supporting lookup by key. Unlike an ordered list of guarded alternatives, a simple map does not directly represent sequentially evaluated, potentially repeated label expressions with first-match behavior.
Heap data structure 2026-10-20
A tree-based data structure that orders each parent relative to its children so that an extremal value is available at the root. In a max-heap, every parent is at least as large as its children. Heap implementations provide one way to realize a priority queue; the abstract queue and its implementing structure are distinct concepts.
List (abstract data type) 2026-10-20
A list is an ordered collection in which entries may repeat. Removing duplicates would discard information about both multiplicity and, depending on the representation, order. A linked list and an array are different ways to implement list operations.
Rank query 2026-10-20
A character rank query asks how many occurrences of character appear in the first positions of a sequence. A prefix sum array answers a single-character version in constant time after linear preprocessing; a wavelet tree supports many characters more compactly.
Wavelet tree Created 2026-10-20 Updated 2026-11-05
A wavelet tree stores a sequence over an ordered alphabet by repeatedly splitting the alphabet into two parts. At an internal node, a bit vector records zero or one according to each element's part; the children receive the corresponding stable subsequences. The original wavelet-tree construction uses such relative position encodings to support compact indexed access.[ref]
To answer a rank query for character in the first positions, follow the branch containing . Replace by the number of that branch's bits among the current bit vector's first positions. At the leaf, the resulting is the answer. Stable filtering proves the invariant: it is the number of original-prefix elements reaching the current node.
For example, split as and . The string cadaba gives root bit vector 101000 and left subsequence aaba. In its first five characters there are three left-part elements. The left bit vector 0010 contains two zeros among those first three positions, so the number of a occurrences is two. With constant-time bit rank queries and a balanced alphabet split, character rank queries take time.
Suffix array Created 2026-10-20 Updated 2026-10-24
A suffix array stores starting positions of a string's suffixes in lexicographic order. All suffixes starting with a fixed query occupy a consecutive interval. This permits string-searching algorithms to search a compact list of positions instead of storing every suffix explicitly.
Man-in-the-middle attack Created 2026-10-20 Updated 2026-11-05
A man-in-the-middle attack places an adversary between communicating parties so the adversary can relay, replace or originate messages while each party believes it is interacting directly with the other. Unauthenticated key exchange illustrates the risk: an attacker can establish one shared key with each endpoint, then decrypt and re-encrypt forwarded traffic. Strong encryption on both links does not authenticate the intended peer. Authenticated transcripts, validated public-key bindings and session-specific checks address different parts of this threat. The defining feature is control of the communication path and peer substitution, not merely passive observation.
Post-quantum cryptography 2026-10-20
Cryptography intended to remain secure against adversaries with quantum computers. It includes classical algorithms based on problems other than the integer factorization and discrete logarithm problems efficiently treated by Shor's algorithm. A candidate's security still depends on its precise construction, parameters and known attacks; the label alone is not a proof. It is distinct from requiring quantum hardware for quantum key distribution.
Quantum cryptography Created 2026-10-20 Updated 2026-10-24
Cryptographic tasks and protocols using quantum systems. Quantum key distribution is one application; it should not be confused with post-quantum cryptography, which studies classical schemes intended to resist quantum computation.
Two-body scattering cross section Created 2026-10-20 Updated 2026-10-24
For distinguishable final particles, the centre-of-momentum frame cross section is the displayed product of the invariant amplitude, incoming flux and relativistic two-body phase space. Initial unpolarized states are averaged; unobserved final polarizations are summed. An isotropic amplitude integrates to . A full-solid-angle integral for identical final particles additionally needs its symmetry factor.
Coordination complex 2026-10-20
A coordination complex contains a central atom, often a metal ion, bound to surrounding ligands in coordination chemistry. The metal oxidation state and the ligand donor types are separate pieces of its description.
A ligand in coordination chemistry is an atom, ion or molecule attached to a central atom through one or more donor sites. This use is distinct from a protein-binding ligand. A neutral CO ligand and an anionic chloride ligand can both donate two electrons in ionic electron counting.
Linkage isomerism 2026-10-20
Linkage isomerism occurs when complexes have the same composition but an ambidentate ligand attaches through different atoms. N-bound and O-bound nitrite provide the classical example. This is a difference in attachment connectivity, rather than the different spatial arrangements of unchanged connectivity in stereoisomers.

There are unlisted articles, also show them or only show them.