The role of various trees in the data structure in the algorithm competition (not yet completed, will write later)

The role of various trees in the data structure in the algorithm competition

nonsense:

Since this fw is always confused about the usage of various trees in the data structure, I can’t remember when to use which one, and csdn didn’t find my favorite blog, so I plan to post a blog QAQ by myself

Regarding this blog, it is not suitable for the completely zero-based Kang. After all, he will not write about the ideas of various tree implementations, but only talk about the functions of various trees.

The tree here is mainly about the tree of interval modification interval query. If it is other types of trees, this blog will not write QAQ (such as trie tree, flower tree, Steiner tree)

In the process of writing, there will inevitably be some mistakes. Please point out the mistakes in the comment area or private message me after seeing the mistakes. I am very grateful~~

Line segment tree

Function

Interval modification/single-point modification/interval query/single-point query

Note: The solution of the large interval of the problem characteristic of the query can be merged from the solution of the small interval (for example, the k-th largest interval cannot use the ordinary line segment tree, but the chairman tree)

Space: generally open 4 times of n

Time: O(n) for building, O(logn) for querying, O(logn) for modifying

Template

The main idea of the topic:

Knowing a sequence, you need to perform the following two operations:

Add k to every number in a certain interval.
Find the sum of each number in an interval.

Code

//https://www.luogu.com.cn/problem/P3372
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e5 + 10;
int a[N];
namespace SegmentTree{
    #define ls rt << 1
#define rs rt << 1 | 1
    #define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
    int len, q, tree[N << 2], lazy[N << 2];
    inline void push_up(int rt) { tree[rt] = tree[ls] + tree[rs]; }
    
    inline void push_down(int rt, int m){
        if(!lazy[rt]) return;
        lazy[ls] + = lazy[rt], lazy[rs] + = lazy[rt];
        tree[ls] + = lazy[rt] * (m - (m >> 1));
        tree[rs] + = lazy[rt] * (m >> 1);
        lazy[rt] = 0;
    }

    static void build(int rt, int l, int r){
        tree[rt] = lazy[rt] = 0;
        if(l == r){
            tree[rt] = a[l]; //!build leaf_node here
            return;
        }
        int mid = l + r >> 1;
        build(lson), build(rson);
        push_up(rt);
    }

    static void update_part(int rt, int l, int r, int L, int R, int val){
        if(l >= L & amp; & amp; r <= R){
            lazy[rt] + = val, tree[rt] + = (r - l + 1) * val;
            return;
        }
        int mid = l + r >> 1;
        push_down(rt, r - l + 1);
        if(mid >= L) update_part(lson, L, R, val);
        if(mid < R) update_part(rson, L, R, val);
        push_up(rt);
    }

    static void update_point(int rt, int l, int r, int pos, int val){
        if(l == r){
            tree[rt] + = val;
            return;
        }
        push_down(rt, r - l + 1);
        int mid = l + r >> 1;
        if(mid >= pos) update_point(lson, pos, val);
        else update_point(rson, pos, val);
        push_up(rt);
    }

    static int query(int rt, int l, int r, int L, int R){
        if(l >= L & amp; & amp; r <= R) return tree[rt];
        int mid = l + r >> 1, ans = 0;
        push_down(rt, r - l + 1);
        if(mid >= L) ans + = query(lson, L, R);
        if(mid < R) ans + = query(rson, L, R);
        return ans;
    }
}
using namespace SegmentTree;
signed main()
{
    cin. tie(0), cout. tie(0);
    ios::sync_with_stdio(false);
    int n,q,t,x,y,k;
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    build(1,1,n);
    while(q--)
    {
        cin>>t>>x>>y;
        if(t==1)
        {
            cin>>k;
            update_part(1,1,n,x,y,k);
        }
        else
            cout<<query(1,1,n,x,y)<<endl;
    }
}

Dynamic open point line segment tree

Function

Range modification/single point modification/single point query/range query

Why it exists: Solve the problem of large intervals or negative numbers (such as weight line segment trees), or the data needs to be discretized and can choose to insert subscripts. At the same time, because it is gradually inserting points, it can also solve the problem of reverse order pairs.

Note: The solution of the large interval of problem characteristics can be merged from the solution of the small interval (for example, the k-th largest interval cannot use the ordinary line segment tree, but the chairman tree)

Space: generally open about 4 times of n (but judging by the minimum and maximum values of the tree, it is best to open a larger size)

Time: To build a tree is to insert n nodes (nlogn), query O(logn), modify O(logn)

Template

Range modification/single point modification/single point query/range query

The main idea of the topic:

Given n numbers, find the number of reversed pairs

Code

//https://www.luogu.com.cn/problem/P3372
#include <bits/stdc++.h>
using namespace std;
#define int long long
namespace SegmentTree{
    const int N = 3e5 + 10;
    int tree[N << 2], lson[N << 2], rson[N << 2], lazy[N << 2], tot = 0;

    inline void push_up(int rt){ tree[rt] = tree[lson[rt]] + tree[rson[rt]]; }
    inline void push_down(int rt, int m){
        if(!lazy[rt]) return;
        if(!lson[rt]) lson[rt] = + + tot;
        if(!rson[rt]) rson[rt] = + + tot;
        lazy[lson[rt]] + = lazy[rt], lazy[rson[rt]] + = lazy[rt];
        tree[lson[rt]] + = lazy[rt] * (m - (m >> 1));
        tree[rson[rt]] + = lazy[rt] * (m >> 1);
        lazy[rt] = 0;
    }

    static void update_part(int & rt , int l, int r, int ql, int qr, int val){
        if(!rt) rt = + + tot;
        if(l >= ql & amp; & amp; r <= qr){
            lazy[rt] += val;
            tree[rt] + = val * (r - l + 1);
            return;
        }
        push_down(rt, r - l + 1);
        int mid = l + r >> 1;
        if(mid >= ql) update_part(lson[rt], l, mid, ql, qr, val);
        if(mid < qr) update_part(rson[rt], mid + 1, r, ql, qr, val);
        push_up(rt);
    }

    static void update_point(int & rt, int l, int r, int pos, int val){
        if(!rt) rt = + + tot;
        if(l == r){
            tree[rt] + = val;
            return;
        }
        int mid = l + r >> 1;
        if(mid >= pos) update_point(lson[rt], l, mid, pos, val);
        else update_point(rson[rt], mid + 1, r, pos, val);
        push_up(rt);
    }

    static int query(int rt, int l, int r, int ql, int qr){
        if(!rt) return 0;
        if(l >= ql & amp; & amp; r <= qr) return tree[rt];
        push_down(rt, r - l + 1);
        int mid = l + r >> 1, ans = 0;
        if(mid >= ql) ans + = query(lson[rt], l, mid, ql, qr);
        if(mid < qr) ans + = query(rson[rt], mid + 1, r, ql, qr);
        return ans;
    }
}//DynamicSegmentTree

signed main(){
    int n,m,root=0,op,x,y,k;
    //int maxr=1e18 + 10,minl=-1e18-10;//You can set the left and right endpoints, in fact, there is no need to open so large, and pay attention to the definition int=long long
    int maxr=n,minl=1;
    cin>>n>>m;
    for(int i=1,x;i<=n;i ++ ){
        cin>>x;
        SegmentTree::update_point(root,minl,maxr,i,x);
    }
    while(m--){
        cin>>op>>x>>y;
        if(op==1){
            cin>>k;
            SegmentTree::update_part(root,minl,maxr,x,y,k);
        }else{
            cout<<SegmentTree::query(1,minl,maxr,x,y)<<endl;
        }
    }
}

Chairman Tree

Function

Interval modification/single-point modification/interval query/single-point query

Why it exists: Each root records a tree, which can support querying historical versions, and use shared data between historical versions to reduce time and space consumption.

Space: Generally open about 16 times n (according to the size of m can be opened larger)

Time: To build a tree is to insert n nodes (nlogn), query O(logn), modify O(logn)

Template

The main idea of the topic:

Given n numbers and m queries, find out what is the kth number from small to large in l to r

Code

//https://www.luogu.com.cn/problem/P3834
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
int root[N], tot;
int lc[N << 5], rc[N << 5], sum[N << 5];
int a[N], b[N], n, m;

namespace cmt{
    void update(int & rt, int pre, int l, int r, int pos, int v){
        rt = + + tot, lc[rt] = lc[pre], rc[rt] = rc[pre], sum[rt] = sum[pre] + 1;
        if(l == r) return;
        int mid = l + r >> 1;
        if(pos <= mid) update(lc[rt], lc[pre], l, mid, pos, v);
        else update(rc[rt], rc[pre], mid + 1, r, pos, v);
    }

    int query(int pre, int post, int l, int r, int k){
        if(l == r) return l;
        int mid = l + r >> 1, cnt = sum[lc[post]] - sum[lc[pre]];
        if(cnt >= k) return query(lc[pre], lc[post], l, mid, k);
        else return query(rc[pre], rc[post], mid + 1, r, k-cnt);
    }
}

signed main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ){
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b + 1, b + 1 + n);
    int n_1 = unique(b + 1, b + 1 + n) - (b + 1);
    for(int i = 1; i <= n; i ++ ) cmt::update(root[i], root[i - 1], 1, n_1, lower_bound(b + 1, b + 1 + n_1, a [i]) - b, 1);
    for(int i = 1; i <= m; i ++ ){
        int l, r, k; cin >> l >> r >> k;
        cout << b[cmt::query(root[l - 1], root[r], 1, n_1, k)] << endl;
    }
    return 0;
}

Cordoli tree

Function

Interval modification/single-point modification/interval query/single-point query

Why it exists: There is an interval flattening operation (line segment tree is also possible), interval power, if the data is random, you can also violently find the kth smallest

Space: don’t need to open the array, just add it

Time: Interval modification, merging, and summation operations are about O(nloglogn). As for seeking the kth person, I still feel unstable (after all, this question is tle)

Template

The main idea of the topic

A set of randomly generated data, perform the following operations

1. Interval l to r plus x

2. The interval l to r is assigned as x

3. Output the xth smallest number in the interval l to r

4. Output the value of x power and modulo y of each number in l to r

Code

//https://www.luogu.com.cn/problem/CF896C
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll MOD = 1000000007;
const ll MAXN = 100005;

struct Node {
    ll l, r;//l and r indicate the start and end of this section
    mutable ll v;//v indicates the same value of all elements in this segment

    Node(ll l, ll r = 0, ll v = 0) : l(l), r(r), v(v) {}

    bool operator<(const Node &a) const {
        return l < a.l;//Sort according to the left endpoint of each paragraph
    }
};

ll n, m, seed, vmax, a[MAXN];
set<Node> s;

//Using pos to cut, find an interval containing pos, and divide it into two halves [l,pos-1],[pos,r]
set<Node>::iterator split(int pos) {
    set<Node>::iterator it = s.lower_bound(Node(pos));
    if (it != s.end() & amp; & amp; it->l == pos) {
        return it;
    }
    it--;
    if (it->r < pos) return s. end();
    ll l = it->l;
    ll r = it->r;
    ll v = it->v;
    s. erase(it);
    s.insert(Node(l, pos - 1, v));
    //The insert function returns pair, where first is the iterator of the newly inserted node
    return s.insert(Node(pos, r, v)).first;
}

/*
 * Note here that itr must be calculated first.
 * For example, the interval is [1,4] now, if you want to add [1,2], if you split(1) first
 * Then the returned itl is [1,4], but when calculating itr in the next step, this interval will be deleted and split into [1,2] and [3,4]
 * Then the itl pointer is released
 * */
void add(ll l, ll r, ll x) {
    set<Node>::iterator itr = split(r + 1), itl = split(l);
    for (set<Node>::iterator it = itl; it != itr; + + it) {
        it->v += x;
    }
}

void assign(ll l, ll r, ll x) {
    set<Node>::iterator itr = split(r + 1), itl = split(l);
    s. erase(itl, itr);
    s.insert(Node(l, r, x));
}

struct Rank {
    ll num, cnt;

    bool operator<(const Rank &a) const {
        return num < a.num;
    }

    Rank(ll num, ll cnt) : num(num), cnt(cnt) {}
};

ll rnk(ll l, ll r, ll x) {
    set<Node>::iterator itr = split(r + 1), itl = split(l);
    vector<Rank> v;
    for (set<Node>::iterator i = itl; i != itr; + + i) {
        v.push_back(Rank(i->v, i->r - i->l + 1));
    }
    sort(v.begin(), v.end());
    int i;
    for (i = 0; i < v. size(); + + i) {
        if (v[i].cnt < x) {
            x -= v[i].cnt;
        } else {
            break;
        }
    }
    return v[i].num;
}

ll ksm(ll x, ll y, ll p) {
    ll r = 1;
    ll base = x % p;
    while (y) {
        if (y & 1) {
            r = r * base % p;
        }
        base = base * base % p;
        y >>= 1;
    }
    return r;
}

ll calP(ll l, ll r, ll x, ll y) {
    set<Node>::iterator itr = split(r + 1), itl = split(l);
    ll ans = 0;
    for (set<Node>::iterator i = itl; i != itr; + + i) {
        ans = (ans + ksm(i->v, x, y) * (i->r - i->l + 1) % y) % y;
    }
    return ans;
}

ll rnd() {
    ll ret = seed;
    seed = (seed * 7 + 13) % MOD;
    return ret;
}

int main() {
    cin >> n >> m >> seed >> vmax;
    for (int i = 1; i <= n; + + i) {
        a[i] = (rnd() % vmax) + 1;
        s.insert(Node(i, i, a[i]));
    }
    for (int i = 1; i <= m; + + i) {
        ll op, l, r, x, y;
        op = (rnd() % 4) + 1;
        l = (rnd() % n) + 1;
        r = (rnd() % n) + 1;
        if (l > r) swap(l, r);
        if (op == 3)
            x = (rnd() % (r - l + 1)) + 1;
        else
            x = (rnd() % vmax) + 1;
        if (op == 4)
            y = (rnd() % vmax) + 1;
        if (op == 1)
            add(l, r, x);
        else if (op == 2)
            assign(l, r, x);
        else if (op == 3)
            cout << rnk(l, r, x) << endl;
        else
            cout << calP(l, r, x, y) << endl;
    }
    return 0;
}