数据结构篇

目录

• 离散化
• 树状数组(逆序对)
• 线段树(区间和)
• 主席树(静态区间第k大)
• 平衡树(treap / splay)
• KD-tree
• 待补

离散化操作

1.

int num[N]; //离散化后的数组
struct node {
    int x, id;
}T[N];
bool cmp(node a, node b) {
    if(a.x != b.x) return a.x < b.x;
    return a.id < b.id;
}

for(int i = 1; i <= n; i++) {
    cin >> T[i].x;
    T[i].id = i;
}
sort(T + 1, T + n + 1, cmp);
for(int i = 1; i <= n; i++)
    num[T[i].id] = i;

2.

for(int i = 1; i <= n; i++)
    cin >> p[i], b[i] = p[i];
sort(b + 1, b + n + 1);
for(int i = 1; i <= n; i++)
    p[i] = lower_bound(b + 1, b + n + 1, p[i]) - b;

3.

for(int i = 1; i <= n; i++) {
    cin >> a[i];
    b[i] = a[i];
}
sort(b + 1, b + n + 1);
m = unique(b + 1, b + n + 1) - b - 1;

树状数组

template <typename T>
struct binary_indexed_tree{
  int N;
  vector<T> BIT;
  binary_indexed_tree(int N): N(N), BIT(N + 1, 0){
  }
  void add(int i, T x){
    i++;
    while (i <= N){
      BIT[i] += x;
      i += i & -i;
    }
  }
  T sum(int i){
    T ans = 0;
    while (i > 0){
      ans += BIT[i];
      i -= i & -i;
    }
    return ans;
  }
  T sum(int L, int R){
    return sum(R) - sum(L);
  }
};

树状数组求逆序对

    //这里使用离散化方法1
    for(int i = 1; i <= n; i++) {
        cin >> T[i].x;
        T[i].id = i;
    }

    sort(T + 1, T + n + 1, cmp);
    for(int i = 1; i <= n; i++)
        num[T[i].id] = i;

    binary_indexed_tree<int>tr(n + 1);
    ll ans = 0;
    for(int i = 1; i <= n; i++) {
        ans += tr.sum(num[i]);
        tr.add(num[i], 1);
    }
    ans = (ll) n * (n - 1) / 2 - ans;
    cout << ans << '\n';

线段树(区间和为例)

struct node{
    ll sum;
    int lazy;
    node() : sum(0), lazy(0){}
}tree[N << 2];

void build(int k = 1, int l = 1, int r = n)
{
    if(l == r) return void(tree[k].sum = num[l]);
    int mid = (l + r) >> 1;
    build(k<<1, l, mid);
    build(k<<1|1, mid+1, r);
    tree[k].sum = tree[k<<1].sum + tree[k<<1|1].sum;
}

void pushdown(int k, int len)
{
    if(len <= 1) return;
    tree[k<<1].sum += tree[k].lazy * (len - len / 2);
    tree[k<<1].lazy += tree[k].lazy;
    tree[k<<1|1].sum += tree[k].lazy * (len / 2);
    tree[k<<1|1].lazy += tree[k].lazy;
    tree[k].lazy = 0;
}

void update(int l, int r, int d, int k = 1, int cl = 1, int cr = n)
{
    if(cl >= l && cr <= r) return void(tree[k].sum += (cr - cl + 1) * d, tree[k].lazy += d);
    pushdown(k, cr - cl + 1);
    int mid = (cl + cr) >> 1;
    if(mid >= l) update(l, r, d, k<<1, cl, mid);
    if(mid < r) update(l, r, d, k<<1|1, mid+1, cr);
    tree[k].sum = tree[k<<1].sum + tree[k<<1|1].sum;
}

ll query(int l, int r, int k = 1, int cl = 1, int cr = n)
{
    if(cl >= l && cr <= r) return tree[k].sum;
    pushdown(k, cr - cl + 1);
    int mid = (cl + cr) >> 1;
    ll ans = 0;
    if(mid >= l) ans += query(l, r, k<<1, cl, mid);
    if(mid < r) ans += query(l, r, k<<1|1, mid+1, cr);
    return ans;
}

动态开点线段树

#define ls(x) tr[x].ls
#define rs(x) tr[x].rs
#define val(x) tr[x].val
#define mark(x) tr[x].mark
const int N = 2e5 + 7;
int L = 1, R = 1e5, cnt = 1;
struct node{
    ll val, mark;
    int ls, rs;
}tr[N << 2];
void pushdown(int k, int len)
{
    if(len <= 1) return;
    if(!ls(k)) ls(k) = ++cnt;
    if(!rs(k)) rs(k) = ++cnt;
    val(ls(k)) += mark(k) * (len / 2);
    val(rs(k)) += mark(k) * (len - len / 2);
    mark(ls(k)) += mark(k);
    mark(rs(k)) += mark(k);
    mark(k) = 0;
}
void change(int l, int r, int d, int k = 1, int cl = L, int cr = R)
{
    if(cl >= l && cr <= r)
    {
        val(k) += d * (cr - cl + 1);
        mark(k) += d;
    }
    else{
        pushdown(k, cr - cl + 1);
        int mid = (cl + cr - 1) / 2;
        if(l <= mid) change(l, r, d, ls(k), cl, mid);
        if(r > mid) change(l, r, d, rs(k), mid + 1, cr);
        val(k) = val(ls(k)) + val(rs(k));
    }
}
int query(int l, int r, int k = 1, int l = L, int r = R)
{
    if(cl >= l && cr <= r) return val(k);
    pushdown(k, cr - cl + 1);
    int mid = (cl + cr - 1) / 2;
    int ans = 0;
    if(l <= mid) ans += query(l, r, ls(k), cl, mid);
    if(r > mid) ans += query(l, r, rs(k), mid + 1, cr);
    return ans; 
}

主席树

namespace segment_tree
{
#define MAX_N 200010
#define INF 1e9

    struct Node
    {
        int lc, rc;
        int sum;
    } tree[MAX_N * 20];
    int tot, a[MAX_N], root[MAX_N];

    int build(int l, int r)
    {
        int p = ++tot;
        tree[p].sum = 0;
        if(l == r) return p;
        int mid = (l + r) >> 1;
        tree[p].lc = build(l, mid);
        tree[p].rc = build(mid + 1, r);
        return p;
    }

    int insert(int now, int l, int r, int x, int delta)
    {
        int p = ++tot;
        tree[p] = tree[now];
        if(l == r)
        {
            tree[p].sum += delta;
            return p;
        }
        int mid = (l + r) >> 1;
        if(x <= mid) tree[p].lc = insert(tree[now].lc, l, mid, x, delta);
        else tree[p].rc = insert(tree[now].rc, mid + 1, r, x, delta);
        tree[p].sum = tree[tree[p].lc].sum + tree[tree[p].rc].sum;
        return p;
    }

    //询问静态区间第k小
    int ask(int p, int q, int l, int r, int k)
    {
        if(l == r) return l;
        int mid = (l + r) >> 1;
        int lcnt = tree[tree[p].lc].sum - tree[tree[q].lc].sum;
        if(k <= lcnt) return ask(tree[p].lc, tree[q].lc, l, mid, k);
        else return ask(tree[p].rc, tree[q].rc, mid + 1, r, k - lcnt);
    }
}

using namespace segment_tree;

求静态区间第k小

    cin >> n >> q;
    //这里使用离散化方法3
    for(int i = 1; i <= n; i++) {
        cin >> num[i];
        a[i] = num[i];
    }
    sort(a + 1, a + n + 1);
    m = unique(a + 1, a + n + 1) - a - 1;
    root[0] = build(1, m);
    for(int i = 1; i <= n; i++)//n个数字
    {
        int x = lower_bound(a + 1, a + m + 1, num[i]) - a; // 离散化后的值
        root[i] = insert(root[i - 1], 1, m, x, 1); // 值为x的数增加1个
    }
    while(q--) {
        int l, r, k;
        cin >> l >> r >> k;
        int ans = ask(root[r], root[l - 1], 1, m, k);
        cout << a[ans] << '\n';
    }

平衡树

这里讨论的平衡树主要是treap和splay
treap

struct node {
    int l, r;
    int key;
    int val;
    int cnt;
    int sz;
}tr[N];

int root, idx;

void pushup(int p) {
    tr[p].sz = tr[tr[p].l].sz + tr[tr[p].r].sz + tr[p].cnt;
}

int get_node(int key) {
    tr[++idx].key = key;
    tr[idx].val = rand();
    tr[idx].cnt = 1;
    tr[idx].sz = 1;
    return idx;
}

void build() {
    get_node(-inf);
    get_node(inf);
    root = 1;
    tr[root].r = 2;
    pushup(root);
}

//右旋
void zig(int &p) {
    int q = tr[p].l;
    tr[p].l = tr[q].r;
    tr[q].r = p;
    p = q;
    pushup(tr[p].r);
    pushup(p);
}

//左旋
void zag(int &p) {
    int q = tr[p].r;
    tr[p].r = tr[q].l;
    tr[q].l = p;
    p = q;
    pushup(tr[p].l);
    pushup(p);
}

void insert(int &p, int key) {
    if(!p) p = get_node(key);
    else if(tr[p].key == key) tr[p].cnt++;
    else if(tr[p].key > key) {
        insert(tr[p].l, key);
        if(tr[tr[p].l].val > tr[p].val) zig(p);
    } else {
        insert(tr[p].r, key);
        if(tr[tr[p].r].val > tr[p].val) zag(p);
    }
    pushup(p);
}

void remove(int &p, int key) {
    if(!p) return;
    if(tr[p].key == key) {
        if(tr[p].cnt > 1) tr[p].cnt--;
        else if(tr[p].l || tr[p].r) {

            if(!tr[p].r || tr[tr[p].l].val > tr[tr[p].r].val) {
                zig(p);
                remove(tr[p].r, key);
            } else {
                zag(p);
                remove(tr[p].l, key);
            }
        } else p = 0;
    } else if(tr[p].key > key) remove(tr[p].l, key);
    else remove(tr[p].r, key);
    pushup(p);
}

int get_rank(int p, int key) {
    if(!p) return 0;
    if(tr[p].key == key) return tr[tr[p].l].sz + 1;
    if(tr[p].key > key) return get_rank(tr[p].l, key);
    return tr[tr[p].l].sz + tr[p].cnt + get_rank(tr[p].r, key);
}

int kth(int p, int k) {
    if(!p) return inf;
    if(tr[tr[p].l].sz >= k) return kth(tr[p].l, k);
    if(tr[tr[p].l].sz + tr[p].cnt >= k) return tr[p].key;
    return kth(tr[p].r, k - tr[tr[p].l].sz - tr[p].cnt);
}

int get_prev(int p, int key) {
    if(!p) return -inf;
    if(tr[p].key >= key) return get_prev(tr[p].l, key);
    return max(tr[p].key, get_prev(tr[p].r, key));
}

int get_next(int p, int key) {
    if(!p) return inf;
    if(tr[p].key <= key) return get_next(tr[p].r, key);
    return min(tr[p].key, get_next(tr[p].l, key));
}

splay

int rt, tot, fa[N], ch[N][2], val[N], cnt[N], sz[N];

struct Splay {
  void maintain(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x]; }

  bool get(int x) { return x == ch[fa[x]][1]; }

  void clear(int x) {
    ch[x][0] = ch[x][1] = fa[x] = val[x] = sz[x] = cnt[x] = 0;
  }

  void rotate(int x) {
    int y = fa[x], z = fa[y], chk = get(x);
    ch[y][chk] = ch[x][chk ^ 1];
    if (ch[x][chk ^ 1]) fa[ch[x][chk ^ 1]] = y;
    ch[x][chk ^ 1] = y;
    fa[y] = x;
    fa[x] = z;
    if (z) ch[z][y == ch[z][1]] = x;
    maintain(x);
    maintain(y);
  }

  void splay(int x) {
    for (int f = fa[x]; f = fa[x], f; rotate(x))
      if (fa[f]) rotate(get(x) == get(f) ? f : x);
    rt = x;
  }

  void ins(int k) {
    if (!rt) {
      val[++tot] = k;
      cnt[tot]++;
      rt = tot;
      maintain(rt);
      return;
    }
    int cur = rt, f = 0;
    while (1) {
      if (val[cur] == k) {
        cnt[cur]++;
        maintain(cur);
        maintain(f);
        splay(cur);
        break;
      }
      f = cur;
      cur = ch[cur][val[cur] < k];
      if (!cur) {
        val[++tot] = k;
        cnt[tot]++;
        fa[tot] = f;
        ch[f][val[f] < k] = tot;
        maintain(tot);
        maintain(f);
        splay(tot);
        break;
      }
    }
  }

  int rk(int k) {
    int res = 0, cur = rt;
    while (1) {
      if (k < val[cur]) {
        cur = ch[cur][0];
      } else {
        res += sz[ch[cur][0]];
        if (k == val[cur]) {
          splay(cur);
          return res + 1;
        }
        res += cnt[cur];
        cur = ch[cur][1];
      }
    }
  }

  int kth(int k) {
    int cur = rt;
    while (1) {
      if (ch[cur][0] && k <= sz[ch[cur][0]]) {
        cur = ch[cur][0];
      } else {
        k -= cnt[cur] + sz[ch[cur][0]];
        if (k <= 0) {
          splay(cur);
          return val[cur];
        }
        cur = ch[cur][1];
      }
    }
  }

  int pre() {
    int cur = ch[rt][0];
    if (!cur) return cur;
    while (ch[cur][1]) cur = ch[cur][1];
    splay(cur);
    return cur;
  }

  int nxt() {
    int cur = ch[rt][1];
    if (!cur) return cur;
    while (ch[cur][0]) cur = ch[cur][0];
    splay(cur);
    return cur;
  }

  void del(int k) {
    rk(k);
    if (cnt[rt] > 1) {
      cnt[rt]--;
      maintain(rt);
      return;
    }
    if (!ch[rt][0] && !ch[rt][1]) {
      clear(rt);
      rt = 0;
      return;
    }
    if (!ch[rt][0]) {
      int cur = rt;
      rt = ch[rt][1];
      fa[rt] = 0;
      clear(cur);
      return;
    }
    if (!ch[rt][1]) {
      int cur = rt;
      rt = ch[rt][0];
      fa[rt] = 0;
      clear(cur);
      return;
    }
    int cur = rt;
    int x = pre();
    fa[ch[cur][1]] = x;
    ch[x][1] = ch[cur][1];
    clear(cur);
    maintain(rt);
  }
} tree;
//ps : 一般来说，找前驱和后继的时候通常都会先tree.ins(x), 找到val[tree.pre / nxt()]之后再tree.del(x)

KD-tree

~这个其实我还不会，没看懂qwq~
但是具体来说，就是在k维空间中的n的点中找距离x最近的一个点
感觉KD-tree的可扩展性还是很强的

namespace kd_tree
{
#define SIZE 50010
#define MAX_K 5
#define sqr(x) ((x)*(x))
    int index, k;

    struct Node
    {
        int x[MAX_K];

        bool operator<(const Node &b) const
        {
            return x[index] < b.x[index];
        }
    } p[SIZE];

    typedef pair<double, Node> dn;
    priority_queue<dn> q;

    struct KD_tree
    {
        int sz[SIZE << 2];
        Node nd[SIZE << 2];

        void build(int i, int l, int r, int d)
        {
            if(l > r) return;
            int mid = (l + r) >> 1;
            index = d % k;
            sz[i] = r - l;
            sz[i << 1] = sz[i << 1 | 1] = -1;
            nth_element(p + l, p + mid, p + r + 1);
            nd[i] = p[mid];
            build(i << 1, l, mid - 1, d + 1);
            build(i << 1 | 1, mid + 1, r, d + 1);
        }

        void query(int i, int m, int d, Node a)
        {
            if(sz[i] == -1) return;
            dn tmp = dn(0, nd[i]);
            for(int j = 0; j < k; j++)
                tmp.first += sqr(tmp.second.x[j] - a.x[j]);
            int lc = i << 1, rc = i << 1 | 1, dim = d % k, flag = 0;
            if(a.x[dim] >= nd[i].x[dim]) swap(lc, rc);
            if(~sz[lc]) query(lc, m, d + 1, a);
            if(q.size() < m) q.push(tmp), flag = 1;
            else
            {
                if(tmp.first < q.top().first) q.pop(), q.push(tmp);
                if(sqr(a.x[dim] - nd[i].x[dim]) < q.top().first) flag = 1;
            }
            if(~sz[rc] && flag) query(rc, m, d + 1, a);
        }
    };
}

kd_tree::KD_tree kdt;

其他的待补…