每天有10亿人的登录，用户登出时，会输出登入时间和登出时间，平均在线时长为1小时，如何快速的求某一秒钟内的在线人数。
思路:可以用线段树来处理。在知道(loginTime,logoutTime)时，将区间(loginTime, logoutTime-1)加1。
具体的线段树代码 如下：
#pragma once const int N = 2 * 24 * 3600; #define LSON(o) (o << 1) #define RSON(o) ((o << 1) + 1) class Node { public: void setNode(int l, int r, int add, int sum) { this->l = l; this->r = r; this->add = add; this->sum = sum; } private: friend class RMQ; int l, r; int add; int sum; }; Node node[N]; class RMQ { public: RMQ() { tree = node; } void build(int o, int left, int right) { if (left == right) { tree[o].setNode(left, right, 0, 0); } else { int mid = (left + right) >> 1; build(o * 2, left, mid); build(o * 2 + 1, mid + 1, right); tree[o].l = left; tree[o].r = right; tree[o].add = 0; tree[o].sum = 0; } } void update(int o, int left, int right, int v) { if (left <= tree[o].l && right >= tree[o].r) { tree[o].add += v; } else { int mid = (tree[o].l + tree[o].r) >> 1; if (left <= mid) update(LSON(o), left, right, v); if (right > mid) update(RSON(o), left, right, v); } maintain(o); } int query(int o, int left, int right, int add) { if (left <= tree[o].l && right >= tree[o].r) { return tree[o].sum + add * (tree[o].r - tree[o].l + 1); } else { int mid = (tree[o].l + tree[o].r) >> 1; int result = 0; if (left <= mid) { result += query(LSON(o), left, right, add + tree[o].add); } if (right > mid) { result += query(RSON(o), left, right, add + tree[o].add); } return result; } } private: void pushdown(int o) { if (tree[o].add > 0) { tree[LSON(o)].add += tree[o].add; tree[RSON(o)].add += tree[o].add; tree[o].add = 0; } } void maintain(int o) { if (tree[o].r > tree[o].l) { tree[o].sum = tree[LSON(o)].sum + tree[RSON(o)].sum; } tree[o].sum += tree[o].add * (tree[o].r - tree[o].l + 1); } Node* tree; };