给定一个数据序列（可能有重复项）和一个固定大小的移动窗口，每次迭代从数据序列的开始位置移动窗口，使得：
（1）最老的数据元素从窗口中移除，并将新的数据元素推入窗口
（2）在每个移动时，在窗口内查找数据的中位数。
以下帖子没有帮助：
我的想法：
使用 2 个堆来保存中位数。在窗口内部，对窗口内的数据进行排序。在第一次迭代中，小根堆保存较大的部分，大根堆保存较小的部分。如果窗口中的数据数量为奇数，则大根堆返回中位数，否则两个堆的顶部元素的算术平均值是中位数。
当将新数据推入窗口时，从堆中删除最旧的数据，并将新数据与大根堆和小根堆的顶部元素进行比较，以决定将数据放置在哪个堆中。然后，像第一次迭代中那样找到中位数。
但是，在堆中查找数据元素是一个问题。堆是二叉树而不是二叉搜索树。
是否可能用 O(n) 或 O(n * lg m) 解决，其中 m 是窗口大小，并且空间：O(1)？
非常感谢任何帮助。
谢谢。
O(n*lg m)很简单：
只需使用两个std::set来维护窗口，一个用于存储下半部分，一个用于存储上半部分。插入新元素的时间复杂度为O(lg m)，查找和删除旧元素的时间复杂度也是如此。使用你在问题中描述的方法确定中位数的时间复杂度为O(1)。
当你将窗口滑过序列时，在每次迭代中，需要移除窗口外的物品(O(lg m)), 插入新的物品(O(lg m))并计算中位数(O(1))，总时间复杂度为O(n lg m)。
当然，该解决方案使用了O(m)的空间，但我认为你无法不存储窗口的内容。
m/2-1元素，另一个用于较大的m/2-1元素，并存储中位数。当您移动窗口时：**1.从较低或较高的树中删除旧元素（O(log m)），然后2.*将新元素插入到较低或较高的树中，基于它是否小于或大于中位数。如果其中一个树现在有太多元素，则删除最大值(对于较低)或最小值(对于较高)*元素(O(log m))，将其称为新中位数，并将旧中位数插入到另一个树中(O(log m))。总计O(log m)。 - BlueRaja - Danny PflughoeftO(1) - 只需保留对它们的引用即可。C++ 的 stl::set 已经通过 *stl::set::rbegin() 实现了这一点。 - BlueRaja - Danny Pflughoeft<父节点，右子树为>，而是将左子树设为<=，右子树为>。每个节点仍应具有两个（或更少）子节点。 - BlueRaja - Danny Pflughoeft我针对“C语言中的滚动中位数”问题给出了答案。
我找不到一个具有次序统计结构的现代C++数据结构的实现，因此最终采用了top coders链接中的两种想法（匹配编辑：向下滚动到FloatingMedian）。
第一种想法将数据分成两个数据结构（堆、multiset等），每个插入/删除的O(ln N)不允许量化动态地改变而没有巨大的成本。也就是说，我们可以有一个滚动中位数或一个滚动75%，但不能同时拥有。
第二种想法使用线段树进行插入/删除/查询，其复杂度为O(ln N)，但更加灵活。最好的是，“N”是您的数据范围大小。因此，如果您的滚动中位数具有100万项窗口，但您的数据变化从1..65536，则每次移动100万个滚动窗口只需要16个操作！ （并且您只需要65536 * sizeof（计数类型）字节，例如65536 * 4）。
就在我准备放弃之前，我发现stdlibc++包含有序统计树！！！
这些树具有两个关键操作：
iter = tree.find_by_order(value)
order = tree.order_of_key(value)
#if !defined(GNU_ORDER_STATISTIC_SET_H)
#define GNU_ORDER_STATISTIC_SET_H
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// A red-black tree table storing ints and their order
// statistics. Note that since the tree uses
// tree_order_statistics_node_update as its update policy, then it
// includes its methods by_order and order_of_key.
template <typename T>
using t_order_statistic_set = __gnu_pbds::tree<
T,
__gnu_pbds::null_type,
std::less<T>,
__gnu_pbds::rb_tree_tag,
// This policy updates nodes' metadata for order statistics.
__gnu_pbds::tree_order_statistics_node_update>;
#endif //GNU_ORDER_STATISTIC_SET_H
和hc_的答案相同，但是不使用股票BST，而是使用每个节点都有该子树中元素计数的版本。这样查找中位数的时间复杂度为O(log(m))。
我附上了我的线段树（请参见我的其他帖子），它可以非常高效地查询计数的频率分布。
这实现了以下数据结构：
|-------------------------------|
|---------------|---------------|
|-------|-------|-------|-------|
|---|---|---|---|---|---|---|---|
0 1 2 3 4 5 6 7
#if !defined(SEGMENT_TREE_H)
#define SEGMENT_TREE_H
#include <cassert>
#include <array>
#include <algorithm>
#include <set>
#ifndef NDEBUG
#include <set>
#endif
template<typename COUNTS, unsigned BITS>
class t_segment_tree
{
static const unsigned cnt_elements = (1 << BITS);
static const unsigned cnt_storage = cnt_elements << 1;
std::array<COUNTS, cnt_elements * 2 - 1> counts;
unsigned count;
#ifndef NDEBUG
std::multiset<unsigned> elements;
#endif
public:
//____________________________________________________________________________________
// constructor
//____________________________________________________________________________________
t_segment_tree(): count(0)
{
std::fill_n(counts.begin(), counts.size(), 0);
}
//~t_segment_tree();
//____________________________________________________________________________________
// size
//____________________________________________________________________________________
unsigned size() const { return count; }
//____________________________________________________________________________________
// constructor
//____________________________________________________________________________________
void insert(unsigned x)
{
#ifndef NDEBUG
elements.insert(x);
assert("...............This element is too large for the number of BITs!!..............." && cnt_elements > x);
#endif
unsigned ii = x + cnt_elements;
while (ii)
{
++counts[ii - 1];
ii >>= 1;
}
++count;
}
//____________________________________________________________________________________
// erase
// assumes erase is in the set
//____________________________________________________________________________________
void erase(unsigned x)
{
#ifndef NDEBUG
// if the assertion failed here, it means that x was never "insert"-ed in the first place
assert("...............This element was not 'insert'-ed before it is being 'erase'-ed!!..............." && elements.count(x));
elements.erase(elements.find(x));
#endif
unsigned ii = x + cnt_elements;
while (ii)
{
--counts[ii - 1];
ii >>= 1;
}
--count;
}
//
//____________________________________________________________________________________
// kth element
//____________________________________________________________________________________
unsigned operator[](unsigned k)
{
assert("...............The kth element: k needs to be smaller than the number of elements!!..............." && k < size());
unsigned ii = 1;
while (ii < cnt_storage)
{
if (counts[ii - 1] <= k)
k -= counts[ii++ - 1];
ii <<= 1;
}
return (ii >> 1) - cnt_elements;
}
};
#endif