Skip to content
数据结构

树状数组

cpp
template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;
    Fenwick(int n_ = 0) {
        init(n_);
    }
    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }
    void add(int i, const T &v) {
        while(i<n) {
            a[i]+=v;
            i+=i&-i;
        }
    }
    T get(int i) {
        T ans{};
        while(i>0){
            ans+=a[i];
            i-=i&-i;
        }
        return ans;
    }
    T range(int l, int r) {
        return get(r)-get(l-1);
    }
    int selectKth(const T &k) {
        int x = 0;
        T cur{};
        for (int i = 1 << std::__lg(n); i; i /= 2) {
            if (x + i <= n && cur + a[x + i - 1] <= k) {
                x += i;
                cur = cur + a[x - 1];
            }
        }
        return x;
    }
};

对顶堆

这里维护第k大(维护第k小对元素取负即可)

  • 建立一大一小两个堆
  • 记住小维护大,大维护小
  • 小根堆用于维护值前k大的元素
  • 大根堆用于维护值小于k大的元素
  • 维护,一个堆超大小了就取出来丢到另外一个堆即可
  • 插入的话,小于小根堆堆顶的元素就丢到大根堆,否则相反,然后维护
  • 记得python中大根堆都是相反数
  • 记得每次插入完都要update一下,有些题目会改变k,所以就不写死了insert后调用update

反悔堆

要最小化决策数量,一种决策代价低但是效果差(1-10效果,同种之间值不定),一种决策代价高但是效果好(100-200效果),我们先贪心的选代价低的决策,然后当不行的时候反悔最小的效果的决策并改为高代价的决策

题目

cpp
class Solution {
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
        vector<int> end(2);
        end[0]=target;
        end[1]=0;
        stations.push_back(end);
        sort(stations.begin(),stations.end());
        priority_queue<int> q;
        int cnt=0;
        int now=0;
        for(auto s:stations){
            int pos=s[0],fuel=s[1];
            if(pos>target)break;
            int d=pos-now;
            while(!q.empty()&&startFuel<d){
                startFuel+=q.top();
                q.pop();
                cnt++;
            }
            if(startFuel<d)return -1;
            startFuel-=d;
            now=pos;
            q.push(fuel);
        }
        return cnt;
    }
};

ST表

cpp
int A[N], f[__lg(N) + 1][N];
void init(int n) {
    for (int i = 1; i <= n; ++i)
        f[0][i] = A[i];
    for (int i = 1; i <= __lg(n); ++i)
        for (int j = 1; j + (1 << i) - 1 <= n; ++j)
            f[i][j] = max(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]);
}
int query(int l, int r) {
    int s = __lg(r - l + 1);
    return max(f[s][l], f[s][r - (1 << s) + 1]);
}

线段树

Lazy线段树

  • todo标记数组
  • _do用于打上标记
  • _down用于下传标记
  • _up用于维护树的信息上传

只需要修改这三个函数以及查询函数即可

一般会对有todo的区间节点依然加上todo影响的值,这样查询的时候就不用额外处理下标

对于多种lazy标记的时候,需要注意两个点:

  • 规定好标记处理的先后顺序
  • 尽量利用标记的相互转化,而不是直接下传
cpp
int val[N];
int node[N << 2], todo[N << 2];

void _do(int p, int size, int v)
{
    node[p] += v * size;
    todo[p] += v;
}

void _down(int p, int l, int r)
{
    if (l >= r)
        return;
    int size = r - l + 1;
    _do(p * 2, size - size / 2, todo[p]);
    _do(p * 2 + 1, size / 2, todo[p]);
    todo[p] = 0;
}

void _up(int p)
{
    node[p] = node[p * 2] + node[p * 2 + 1];
}

void build(int p, int l, int r)
{
    if (l == r)
    {
        node[p] = val[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
    _up(p);
}

void update(int p, int l, int r, int L, int R, int v)
{
    if (L <= l and r <= R)
    {
        _do(p, r - l + 1, v);
        return;
    }
    int mid = (l + r) >> 1;
    _down(p, l, r);
    if (mid >= L)
        update(p * 2, l, mid, L, R, v);
    if (mid < R)
        update(p * 2 + 1, mid + 1, r, L, R, v);
    _up(p);
}

i64 query(int p, int l, int r, int L, int R)
{
    if (L <= l and r <= R)
    {
        return node[p];
    }
    _down(p, l, r);
    i64 ans = 0;
    int mid = (l + r) >> 1;
    if (mid >= L)
        ans += query(p * 2, l, mid, L, R);
    if (mid < R)
        ans += query(p * 2 + 1, mid + 1, r, L, R);
    return ans;
}

单调栈

维护NGE,或者递增递减关系(比如子序列最大字典序)等

平衡树

基于pb_ds版

cpp
#ifdef USE_PD
#include <ext/pb_ds/assoc_container.hpp> //容器库
#include <ext/pb_ds/tree_policy.hpp>     //各种树
#include <ext/pb_ds/hash_policy.hpp>     //哈希表
using namespace __gnu_pbds;
#endif
cpp
tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> p;
// upper_bound的实际定义为寻找序列中第一个不满足比较函数的元素,lower_bound的实际定义为寻找序列中最后一个满足比较函数的元素
// 故std::less改为std::less_equal(允许元素重复)后两函数返回结果互换
// 同时find函数无法正确使用
int n = read();
for (int i = 0; i < n; i++)
{
    int opt = read(), x = read();
    if (opt == 1)
    {
        p.insert(x);
    }
    if (opt == 2)
    {
        auto ops = p.upper_bound(x);
        p.erase(ops);
    }
    if (opt == 3)
    {
        print(p.order_of_key(x) + 1);
    }
    if (opt == 4)
    {
        print(*p.find_by_order(x - 1));
    }
    if (opt == 5)
    {
        auto pos = p.upper_bound(x);
        print(*(--pos));
    }
    if (opt == 6)
    {
        auto pos = p.lower_bound(x);
        print(*(pos));
    }
}