Sliding Median

Solución 1: Mantener dos multiconjuntos

Para hallar la mediana ordenada de una ventana deslizante, podemos guardar la ventana en dos conjuntos: uno con los valores inferiores de la ventana y el otro con los valores superiores. Si nos aseguramos de que el tamaño del conjunto inferior sea siempre mayor o igual que el del superior, entonces el elemento más grande del conjunto inferior será la mediana. Esto funciona para todos los tamaños de ventanas. En ventanas impares, el tamaño del conjunto inferior será uno más que el superior, por lo tanto su elemento más grande será la mediana. En ventanas pares, el problema pide el menor de los dos valores centrales, así que esta estrategia sigue funcionando.

Para implementar, necesitamos una función que maneje insertar y eliminar elementos de la ventana. Para insertar, comparamos el valor entrante con la mediana actual y lo colocamos en el conjunto superior si es mayor que la mediana; en caso contrario, lo ponemos en el conjunto inferior. Si un conjunto se llena por encima de su tamaño máximo, transferimos un elemento al otro conjunto. Borrar es más simple: solo hay que hallar el elemento y eliminarlo.

Implementación

Complejidad temporal: $\mathcal{O}(N\log N)$

C++


#include <algorithm>
#include <iostream>
#include <set>
using namespace std;
 
long N, M;
long arr[200010];
multiset<long> up;
multiset<long> low;
 
void ins(long val) {         // insertar val en los conjuntos
	long a = *low.rbegin();  // mediana actual
	if (a < val) {
		up.insert(val);
		if (up.size() > M / 2) {
			low.insert(*up.begin());
			up.erase(up.begin());
		}
	} else {
		low.insert(val);
		if (low.size() > (M + 1) / 2) {
			up.insert(*low.rbegin());
			low.erase(--low.end());
		}
	}
}
 
void er(long val) {  // borrar de los conjuntos
	if (up.find(val) != up.end()) up.erase(up.find(val));
	else low.erase(low.find(val));
	if (low.empty()) {
		low.insert(*up.begin());
		up.erase(up.begin());
	}
}
 
int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) cin >> arr[i];
	low.insert(arr[0]);
	for (int i = 1; i < M; i++) ins(arr[i]);
	cout << *low.rbegin() << " ";
	for (long i = M; i < N; i++) {
		if (M == 1) {
			ins(arr[i]);
			er(arr[i - M]);
		} else {
			er(arr[i - M]);
			ins(arr[i]);
		}
		cout << *low.rbegin() << " ";
	}
	cout << endl;
}

Solución 2: Árbol de Fenwick

Podemos usar un Árbol de Fenwick para simular un árbol de estadísticas de orden / indexed set.

El arreglo de Fenwick (llamémoslo fa) se puede tratar como un arreglo de frecuencias. Por ejemplo, si se inserta 5 en la ventana, fa[5] += 1. Esto nos permite hacer búsqueda binaria de un entero $x$ tal que

\left(\sum_{i=1}^{x} \texttt{fa[i]}\right)\geq \lceil k/2 \rceil \text{ and } \left(\sum_{i=1}^{x-1}\texttt{fa[i]}\right) <\lceil k/2 \rceil

y hallar $k$ a partir de ahí. Claramente, los valores del arreglo habría que comprimirlos, ya que un arreglo de tamaño $10^9$ es inviable. También habrá un factor $\log$ extra por usar la operación sum del Árbol de Fenwick, dando una complejidad temporal total de $\mathcal{O}(n\log^2{n})$ . Nótese que una cota superior más precisa es $\mathcal{O}((n-k+1) \cdot \log^2{k} + n \log{n})$ (hay $(n-k+1)$ ventanas), pero es delicado expresar el valor máximo de esto en términos de $n$ y $k$ ; por lo tanto, $\mathcal{O}(n \log^2{n})$ es mejor.

Implementación

C++


#include <bits/stdc++.h>
using namespace std;
 
const int sz = 200005;
int fa[sz], a[sz], bit[sz], n, k;
map<int, int> compressed, decompress;
 
int psum(int x, int sum = 0) {
	for (; x > 0; x -= x & -x) sum += bit[x];
	return sum;
}
void add(int x, int val) {
	for (; x < sz; x += x & -x) bit[x] += val;
}
 
signed main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		compressed[a[i]] = 0;
	}
	int index = 1;
	for (auto &i : compressed) {
		i.second = index++;
		decompress[i.second] = i.first;
	}
	for (int i = 1; i <= n; i++) {
		add(compressed[a[i]], 1);
		if (i >= k + 1) add(compressed[a[i - k]], -1);
		int mid = (k / 2) + (k & 1);
		if (i >= k) {
			int lo = 1, hi = 200003, ans = -1;
			while (lo <= hi) {
				int m = (lo + hi) / 2;
				if (psum(m) >= mid && psum(m - 1) < mid) {
					ans = m;
					break;
				} else if (psum(m) < mid) lo = m + 1;
				else hi = m - 1;
			}
			cout << decompress[ans] << endl;
		}
	}
}

Solución 3: Árbol de estadísticas de orden

Implementación

C++Java

Podemos usar directamente un árbol de estadísticas de orden (C++) para obtener la mediana mientras deslizamos la ventana a lo largo del arreglo en tiempo $\mathcal{O}(n\log n)$ .


#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
 
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
 
int n, k, t, a[200005];
 
int main() {
	cin >> n >> k;
	ordered_set oset;
	for (int i = 0; i < n; i++) {
		int u;
		cin >> u;
		a[i] = u;
		oset.insert({u, t++});
		if (i >= k) { oset.erase(oset.lower_bound({a[i - k], 0})); }
		if (i >= k - 1) { cout << (*oset.find_by_order((k - 1) / 2)).first << endl; }
	}
}

Podemos usar un árbol de estadísticas de orden modificado para obtener la mediana mientras deslizamos la ventana a lo largo del arreglo en tiempo $\mathcal{O}(n\log n)$ . Para manejar correctamente los duplicados, modificamos la implementación estándar de CLRS guardando el conteo de cada valor dentro del nodo. Luego lo usamos al buscar un elemento de un rango específico:


OS-SELECT(x, i):
    if (i < x.left.size + 1)
	return OS-SELECT(x.left, i);
    else if (i > x.left.size + x.count)
	return OS-SELECT(x.right, i - x.left.size - x.count);
    else
	return x;


import java.io.*;
 
public class Main {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();
		int N = io.nextInt();
		int K = io.nextInt();
		int[] arr = new int[N];
		for (int i = 0; i < N; i++) arr[i] = io.nextInt();
 
		OrderedMultiset<Integer> slidingWindow = new OrderedMultiset<>();
		for (int i = 0; i < K; i++) slidingWindow.insert(arr[i]);
 
		final int medianRank = (int)Math.ceil(K / 2.0f);
		io.print(slidingWindow.findByOrder(medianRank));
 
		for (int i = K; i < N; i++) {
			slidingWindow.erase(arr[i - K]);
			slidingWindow.insert(arr[i]);
 
			io.print(" " + slidingWindow.findByOrder(medianRank));
		}
 
		io.close();
	}
 
	// CodeSnip{Kattio}
 
	// BeginCodeSnip{OrderedMultiset}
	static class OrderedMultiset<K extends Comparable<K>> {
		private class RBNode {
			K key;
			int count;
			RBNode left, right;
			RBNode parent;
			boolean color;
			int size;
 
			static final boolean RED = true;
			static final boolean BLACK = false;
		}
 
		private final RBNode nil = new RBNode();
		private RBNode root = this.nil;
 
		public void insert(final K k) { RB_INSERT(k, 1); }
 
		public void erase(final K k) {
			final RBNode found = TREE_SEARCH(this.root, k);
			if (found != null) RB_DELETE(found, 1);
		}
 
		public K findByOrder(final int rank) { return OS_SELECT(this.root, rank).key; }
 
		private RBNode TREE_SEARCH(final RBNode x, final K k) {
			if (x == this.nil) return null;
			if (x.key.equals(k)) return x;
			if (x.key.compareTo(k) < 0) return TREE_SEARCH(x.right, k);
 
			return TREE_SEARCH(x.left, k);
		}
 
		private RBNode TREE_MINIMUM(RBNode x) {
			while (x.left != this.nil) x = x.left;
 
			return x;
		}
 
		private void RB_INSERT(final K k, final int cnt) {
			final RBNode z = new RBNode();
			z.key = k;
			z.count = cnt;
			z.size = cnt;
 
			RBNode x = this.root;
			RBNode y = this.nil;
			while (x != this.nil) {
				x.size += cnt;
				y = x;
				if (x.key.compareTo(z.key) < 0) x = x.right;
				else if (x.key.compareTo(z.key) > 0) x = x.left;
				else {
					x.count += cnt;
					return;
				}
			}
 
			z.parent = y;
			if (y == this.nil) this.root = z;  // el árbol estaba vacío
			else if (y.key.compareTo(z.key) < 0) y.right = z;
			else y.left = z;
 
			z.left = z.right = this.nil;
			z.color = RBNode.RED;
			RB_INSERT_FIXUP(z);
		}
 
		private void RB_INSERT_FIXUP(RBNode z) {
			while (z.parent.color == RBNode.RED) {
				if (z.parent == z.parent.parent.left) {
					final RBNode y = z.parent.parent.right;
					if (y.color == RBNode.RED) {
						z.parent.color = RBNode.BLACK;
						y.color = RBNode.BLACK;
						z.parent.parent.color = RBNode.RED;
						z = z.parent.parent;
					} else {
						if (z == z.parent.right) {
							z = z.parent;
							LEFT_ROTATE(z);
						}
						z.parent.color = RBNode.BLACK;
						z.parent.parent.color = RBNode.RED;
						RIGHT_ROTATE(z.parent.parent);
					}
				} else {
					final RBNode y = z.parent.parent.left;
					if (y.color == RBNode.RED) {
						z.parent.color = RBNode.BLACK;
						y.color = RBNode.BLACK;
						z.parent.parent.color = RBNode.RED;
						z = z.parent.parent;
					} else {
						if (z == z.parent.left) {
							z = z.parent;
							RIGHT_ROTATE(z);
						}
						z.parent.color = RBNode.BLACK;
						z.parent.parent.color = RBNode.RED;
						LEFT_ROTATE(z.parent.parent);
					}
				}
			}
			this.root.color = RBNode.BLACK;
		}
 
		private void RB_TRANSPLANT(final RBNode u, final RBNode v) {
			if (u.parent == this.nil) this.root = v;
			else if (u == u.parent.left) u.parent.left = v;
			else u.parent.right = v;
 
			v.parent = u.parent;
		}
 
		private void RB_DELETE(final RBNode z, final int cnt) {
			if (z.count > cnt) {
				z.count -= cnt;
				RBNode tmp = z;
				while (tmp != this.nil) {
					tmp.size -= cnt;
					tmp = tmp.parent;
				}
				return;
			}
 
			RBNode x;
			RBNode y = z;
			boolean yOriginalColor = y.color;
			if (z.left == this.nil) {
				x = z.right;
				RB_TRANSPLANT(z, z.right);  // Figure 12.4 (a)
			} else if (z.right == this.nil) {
				x = z.left;
				RB_TRANSPLANT(z, z.left);  // Figure 12.4 (b)
			} else {
				y = TREE_MINIMUM(z.right);
				yOriginalColor = y.color;
				x = y.right;
				if (y.parent == z) {
					x.parent = y;
				} else {  // Figure 12.4 (d)
					RB_TRANSPLANT(y, y.right);
					y.right = z.right;
					y.right.parent = y;
				}
				RB_TRANSPLANT(z, y);  // Figure 12.4 (c)
				y.size = z.size;
				y.left = z.left;
				y.left.parent = y;
				y.color = z.color;
			}
 
			RBNode tmp = x.parent;
			while (tmp != this.nil) {
				tmp.size -= cnt;
				tmp = tmp.parent;
			}
 
			if (yOriginalColor == RBNode.BLACK) RB_DELETE_FIXUP(x);
		}
 
		private void RB_DELETE_FIXUP(RBNode x) {
			while (x != this.root && x.color == RBNode.BLACK) {
				if (x == x.parent.left) {
					// ***** x es un hijo izquierdo ******
					RBNode w = x.parent.right;
					if (w.color == RBNode.RED) {
						x.parent.color = RBNode.RED;
						w.color = RBNode.BLACK;
						LEFT_ROTATE(x.parent);
						w = x.parent.right;
					}
 
					if (w.left.color == RBNode.BLACK && w.right.color == RBNode.BLACK) {
						w.color = RBNode.RED;
						x = x.parent;
					} else {
						if (w.right.color == RBNode.BLACK) {
							w.left.color = RBNode.BLACK;
							w.color = RBNode.RED;
							RIGHT_ROTATE(w);
							w = x.parent.right;
						}
						w.color = x.parent.color;
						x.parent.color = RBNode.BLACK;
						w.right.color = RBNode.BLACK;
						LEFT_ROTATE(x.parent);
						x = this.root;
					}
				} else {
					// ***** x es un hijo derecho ******
					RBNode w = x.parent.left;
					if (w.color == RBNode.RED) {
						x.parent.color = RBNode.RED;
						w.color = RBNode.BLACK;
						RIGHT_ROTATE(x.parent);
						w = x.parent.left;
					}
 
					if (w.left.color == RBNode.BLACK && w.right.color == RBNode.BLACK) {
						w.color = RBNode.RED;
						x = x.parent;
					} else {
						if (w.left.color == RBNode.BLACK) {
							w.right.color = RBNode.BLACK;
							w.color = RBNode.RED;
							LEFT_ROTATE(w);
							w = x.parent.left;
						}
						w.color = x.parent.color;
						x.parent.color = RBNode.BLACK;
						w.left.color = RBNode.BLACK;
						RIGHT_ROTATE(x.parent);
						x = this.root;
					}
				}
			}
			x.color = RBNode.BLACK;
		}
 
		private void LEFT_ROTATE(final RBNode x) {
			final RBNode y = x.right;
			x.right = y.left;
			if (y.left != this.nil) y.left.parent = x;
 
			y.parent = x.parent;
 
			if (x.parent == this.nil) this.root = y;
			else if (x == x.parent.left) x.parent.left = y;
			else x.parent.right = y;
 
			y.left = x;
			x.parent = y;
 
			y.size = x.size;
			x.size = x.left.size + x.right.size + x.count;
		}
 
		private void RIGHT_ROTATE(final RBNode x) {
			final RBNode y = x.left;
			x.left = y.right;
			if (y.right != this.nil) y.right.parent = x;
 
			y.parent = x.parent;
 
			if (x.parent == this.nil) this.root = y;
			else if (x == x.parent.left) x.parent.left = y;
			else x.parent.right = y;
 
			y.right = x;
			x.parent = y;
 
			y.size = x.size;
			x.size = x.left.size + x.right.size + x.count;
		}
 
		private RBNode OS_SELECT(final RBNode x, final int i) {
			if (i < x.left.size + 1) return OS_SELECT(x.left, i);
			else if (i > x.left.size + x.count)
				return OS_SELECT(x.right, i - x.left.size - x.count);
			else return x;
		}
 
		private int OS_RANK(final RBNode x) {
			int rank = x.left.size + 1;
			RBNode y = x;
			while (y != this.root) {
				if (y == y.parent.right) rank += y.parent.left.size + y.parent.count;
 
				y = y.parent;
			}
 
			return rank;
		}
	}
	// EndCodeSnip
}