数据结构

• 并查集
  • 启发式合并
• 树状数组
• 线段树
  • zkw线段树
• ST表
• LRU Cache

并查集

//
// Created by Jiang Yinzuo on 2020/7/18.
// luogup3367

#include <cstdio>

#define MAX_E_NUM 10004

int parents[MAX_E_NUM];

void init(int n) {
    for (int i = 1; i <= n; ++i) {
        parents[i] = i;
    }
}

int find_parent(int v) {
    return parents[v] == v ? v : parents[v] = find_parent(parents[v]);
}

void union_set(int v1, int v2) {
    int p1 = find_parent(v1);
    int p2 = find_parent(v2);
    parents[p1] = p2;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    init(n);
    int op, u, v;
    for (int i = 0; i < m; ++i) {
        scanf("%d %d %d", &op, &u, &v);
        if (op == 1) {
            union_set(u, v);
        } else {
            puts(find_parent(u) == find_parent(v) ? "Y" : "N");
        }
    }
    return 0;
}

启发式合并

//
// Created by Jiang Yinzuo on 2020/7/18.
//

#include <cstdio>
#include <vector>

#define MAX_E_NUM 10004

int parents[MAX_E_NUM];

void init(int n) {
    for (int i = 1; i <= n; ++i) {
        parents[i] = i;
    }
}

/**
 * 路径压缩
 * @param v
 * @return
 */
int find_parent(int v) {
    return parents[v] == v ? v : parents[v] = find_parent(parents[v]);
}

std::vector<int> size(MAX_E_NUM, 1);

/**
 * 启发式合并
 * @param v1
 * @param v2
 */
void union_set(int v1, int v2) {
    int p1 = find_parent(v1);
    int p2 = find_parent(v2);
    if (p1 == p2) return;
    if (size[p1] > size[p2])  // 保证小的合到大的里
        std::swap(p1, p2);
    parents[p1] = p2;
    size[p2] += size[p1];
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    init(n);
    int op, u, v;
    for (int i = 0; i < m; ++i) {
        scanf("%d %d %d", &op, &u, &v);
        if (op == 1) {
            union_set(u, v);
        } else {
            puts(find_parent(u) == find_parent(v) ? "Y" : "N");
        }
    }
    return 0;
}

树状数组

树状数组特点：

• 每一层内，末尾0的个数均相同，第一层0个0，第二次1个0...
• 单点更新：节点x的父节点为x+lowbit(x)
• 区间查询：不停地减去lowbit(x)直到x为0

https://blog.csdn.net/TheWayForDream/article/details/118436732

class TreeArr {
	int n;
	vector<int> inner;

    // ((Not x)+1) And x，即求x的最低位1
	constexpr int lowbit(int x) {
		return x & (-x);
	}

public:
	TreeArr(int _n) : n(_n), inner(_n + 1) {
	}

	void add_val_to_ith(int i, int val) {
		while (i <= n) {
			inner[i] += val;
			i += lowbit(i);
		}
	}

	// [1, i]
	int query_sum_1_to_i(int i) {
		int res = 0;
		while (i > 0) {
			res += inner[i];
			i -= lowbit(i);
		}
		return res;
	}
};

template<const int T>
struct TreeArray {
    int arr[T + 1];

    int lowbit(int x) {
        return x & (-x);
    }

    // add value to arr[i]
    void update(int i, int value) {
        while (i <= T) {
            arr[i] += value;
            i += lowbit(i);
        }
    }

    // query sum of [1, i]
    int query(int i) {
        int total = 0;
        while (i > 0) {
            total += arr[i];
            i -= lowbit(i);
        }
        return total;
    }
};

线段树

zkw线段树

TODO

#include <cstdio>
#include <cstring>

namespace seg_tree {
int arr[50005];
int tree[50005 << 2];

/**
 * 区间查询
 * @param left 线段树节点左边界
 * @param right 线段树节点右边界
 * @param cur_idx 当前线段树节点标记
 * @param arr_left 区间查询左边界
 * @param arr_right 区间查询右边界
 * @return
 */
int query(int left, int right, int cur_idx, const int arr_left, const int arr_right) {
    if (arr_left <= left && right <= arr_right) {
        return tree[cur_idx];
    }

    int mid = (left + right) / 2;

    int result = 0;
    if (arr_left <= mid) {
        result = query(left, mid, cur_idx << 1, arr_left, arr_right);
    }
    if (mid + 1 <= arr_right) {
        result += query(mid + 1, right, (cur_idx << 1) | 1, arr_left, arr_right);
    }

    return result;
}

/**
 * 单点更新线段树
 * @param left 线段树节点左边界
 * @param right 线段树节点右边界
 * @param cur_idx 当前线段树节点标号
 * @param arr_idx 更新的原始数组标号
 * @param value 更新值
 */
void update(int left, int right, int cur_idx, const int arr_idx, const int value) {
    if (left == right) {
        tree[cur_idx] += value;
        return;
    }

    int mid = (left + right) / 2;
    if (arr_idx <= mid) {
        update(left, mid, cur_idx << 1, arr_idx, value);
    } else {
        update(mid + 1, right, (cur_idx << 1) | 1, arr_idx, value);
    }

    tree[cur_idx] = tree[cur_idx << 1] + tree[(cur_idx << 1) | 1];
}

/**
 * 建立线段树
 * @param left 线段树节点左边界
 * @param right 线段树节点右边界
 * @param cur_idx 当前线段树节点标号
 */
void build(int left, int right, int cur_idx) {
    if (left == right) {
        tree[cur_idx] = arr[left];
        return;
    }

    int mid = (left + right) / 2;
    build(left, mid, cur_idx << 1);
    build(mid + 1, right, (cur_idx << 1) | 1);
    tree[cur_idx] = tree[cur_idx << 1] + tree[(cur_idx << 1) | 1];
}
}


int main() {
    int t, n;
    scanf("%d", &t);
    for (int kase = 1; kase <= t; ++kase) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &seg_tree::arr[i]);
        }
        seg_tree::build(1, n, 1);

        printf("Case %d:\n", kase);

        char query_str[6];
        int l, r;
        while (true) {
            scanf("%s", query_str);
            if (strcmp(query_str, "End") == 0) {
                break;
            }
            scanf("%d %d", &l, &r);
            if (strcmp(query_str, "Query") == 0) {
                printf("%d\n", seg_tree::query(1, n, 1, l, r));
            } else if (strcmp(query_str, "Add") == 0) {
                seg_tree::update(1, n, 1, l, r);
            } else if (strcmp(query_str, "Sub") == 0) {
                seg_tree::update(1, n, 1, l, -r);
            }
        }
    }
    return 0;
}

/**
 * luogu3372
 */
#include <cstdio>

long long seq[100008];
long long seg_tree[400008];
long long add_tag[400008] = {0};

/**
 * 建立线段树
 * @param l 区间左端点
 * @param r 区间右端点
 * @param num 序号
 */
void build(int l, int r, int num) {
    if (l == r) {
        seg_tree[num] = seq[l];
        return;
    }

    build(l, (l + r) / 2, num << 1);
    build((l + r) / 2 + 1, r, num << 1 | 1);

    seg_tree[num] = seg_tree[num << 1] + seg_tree[num << 1 | 1];
}

/**
 * 下推懒惰标记
 * @param l 左区间端点
 * @param r 右区间端点
 * @param num 序号
 */
void push_down(int l, int r, int num) {

    if (add_tag[num]) {
        int mid = (r + l) / 2;
        seg_tree[num << 1] += add_tag[num] * (mid - l + 1);
        seg_tree[num << 1 | 1] += add_tag[num] * (r - mid);
        add_tag[num << 1] += add_tag[num];
        add_tag[num << 1 | 1] += add_tag[num];
        add_tag[num] = 0;
    }
}

/**
 * 区间更新
 * @param update_l 更新区间左端点
 * @param update_r 更新区间右端点
 * @param value 更新的值
 * @param l 当前搜索区间左端点
 * @param r 当前搜索区间右端点
 * @param num 线段树序号
 */
void update(int update_l, int update_r, long long value, int l, int r, int num) {
    if (update_l <= l && r <= update_r) {
        seg_tree[num] += (r - l + 1) * value;
        add_tag[num] += value;
        return;
    }

    push_down(l, r, num);

    int mid = (l + r) / 2;
    if (update_l <= mid) {
        update(update_l, update_r, value, l, mid, num << 1);
    }
    if (mid + 1 <= update_r) {
        update(update_l, update_r, value, mid + 1, r, num << 1 | 1);
    }
    seg_tree[num] = seg_tree[num << 1] + seg_tree[num << 1 | 1];
}

/**
 * 区间查询
 * @param query_l 查询区间左端点
 * @param query_r 查询区间右端点
 * @param l 当前搜索区间左端点
 * @param r 当前搜索区间右端点
 * @param num 线段树序号
 * @return 区间查询结果（求区间和）
 */
long long query(int query_l, int query_r, int l, int r, int num) {

    if (query_l <= l && r <= query_r) {
        return seg_tree[num];
    }

    push_down(l, r, num);

    long long result = 0;
    int mid = (l + r) / 2;
    if (query_l <= mid) {
        result += query(query_l, query_r, l, mid, num << 1);
    }
    if (mid + 1 <= query_r) {
        result += query(query_l, query_r, mid + 1, r, num << 1 | 1);
    }
    return result;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &seq[i]);
    }
    build(1, n, 1);
    int op;
    long long x, y, k;
    for (int i = 0; i < m; ++i) {
        scanf("%d", &op);
        if (op == 1) {
            scanf("%lld %lld %lld", &x, &y, &k);
            update(x, y, k, 1, n, 1);
        } else {
            scanf("%lld %lld", &x, &y);
            printf("%lld\n", query(x, y, 1, n, 1));
        }
    }
    return 0;
}

ST表

// luogu3865 ST表模板
// Created by Jiang Yinzuo on 2020/4/11.
//

#include <cstdio>
#include <algorithm>

const int MAX_N = 100009;

int arr[MAX_N];

/**
 * sparse_table[i][j] 表示区间arr中第i个数开始的2^j个数中的最大值
 */
int sparse_table[MAX_N][21];

int LOG_2[MAX_N];

/**
 * log2对数打表
 * @param n 最大值
 */
void calculate_log(int n) {
    LOG_2[1] = 0;
    for (int i = 2; i <= n; ++i) {
        LOG_2[i] = LOG_2[i >> 1] + 1;
    }
}

/**
 * 查询区间f(left, right)最值
 * @param left 左端点
 * @param right 右端点
 * @return 最值
 */
int query(int left, int right) {
    int mid = LOG_2[right - left + 1];

    // 将f(left, right)分成前2^mid个数和后2^mid个数，分别查询
    // f(left, right) = max(f(left, left + 2^mid - 1), f(right - (2^mid-1), right))
    return std::max(sparse_table[left][mid], sparse_table[right - (1 << mid) + 1][mid]);
}

/**
 * 初始化ST表
 * @param arr 输入序列, 下标从1开始
 * @param size 序列长度
 */
void init(int *arr, int size) {

    // 区间arr中第i个数开始的1个数中的最大值就是第i个数
    for (int i = 1; i <= size; ++i) sparse_table[i][0] = arr[i];

    // 依次求2^1, 2^2, 2^3, ... size个数中的最大值
    for (int j = 1; j <= LOG_2[size]; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= size; ++i) {

            // f(i, i + 2^j - 1) = max(f(i, i + 2^(j-1) - 1), f(i + 2^(j-1), i + 2^j - 1)
            sparse_table[i][j] = std::max(sparse_table[i][j-1], sparse_table[i + (1 << (j-1))][j-1]);
        }
    }
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    calculate_log(n);

    for (int i = 1; i <= n; ++i) {
        scanf("%d", &arr[i]);
    }
    init(arr, n);

    int left, right;
    for (int i = 0; i < m; ++i) {
        scanf("%d %d", &left, &right);
        printf("%d\n", query(left, right));
    }
    return 0;
}

LRU Cache

迭代器变量声明: std::unordered_map<int, std::list<Entry>::iterator> map;

牛客BM100 设计LRU缓存结构

#include <cassert>
#include <list>
#include <unordered_map>

class Solution {
    using Entry = std::pair<int, int>;

  public:
    Solution(int capacity) : capacity(capacity) {
    }

    int get(int key) {
        auto it = map.find(key);
        if (it == map.end()) {
            return -1;
        }
        assert(it->first == key);
        auto t = it->second;
        assert(t->first == key);
        int result = t->second;
        entries.erase(t);
        doSet(key, result);
        return result;
    }

    void set(int key, int value) {
        auto it = map.find(key);
        if (it != map.end()) {
            map.erase(it);
        }

        doSet(key, value);
    }
  private:

    void doSet(int key, int value) {
        auto it = entries.emplace_front(key, value);
        map[key] = entries.begin();
        if (entries.size() > capacity) {
            map.erase(entries.back().first);
            entries.pop_back();
            assert(entries.size() == capacity);
        }
    }
    int capacity;

    std::list<Entry> entries;
    std::unordered_map<int, std::list<Entry>::iterator> map;
};