What to do for query problems?

»

13 дней назад, # |

0

Have you considered ordered_set cheese? Since it's applicable to a couple of those problems. Fenwick tree also works in some cases.

→ Ответить

»

Curious69

13 дней назад, # |

0

You missed mo's algorithm and possibly sparse table as well.

→ Ответить

»

NemanjaSo2005

13 дней назад, # |

+9

There is so many variety on what a query problem can be, that there's no one way to solving them. Though as a specialist you should be fine with just prefix sum and binary search. Data structures you mentioned can help too, but I didn't see a lot of them below Div2D and they usually appear only at Div2E and harder problems.

→ Ответить

»

rangerscowboys

12 дней назад, # ^ |

0

This might be from a while ago, but while solving previous Codeforces query problems, they were like question C or D in Div2. I really want to solve 3 in Div2s.

→ Ответить

»

mzv

12 дней назад, # |

0

maybe you can learn fenwick tree?

→ Ответить

»

Red0

12 дней назад, # ^ |

+2

My teacher once told me if you learn segment tree, you will never need to learn fenwick tree... and ig he does have a point lol –– the implementation for segment tree does feel more straightforward, and segment tree does have more capabilities than fenwick tree.

→ Ответить

»

M1ngXu

12 дней назад, # ^ |

0

yes, segment tree > fenwick tree. but since a segment tree "isn't easy to code" you could try to code a fenwick tree which are only about 10-15 lines of code and easy to memorize.

→ Ответить

»

rangerscowboys

12 дней назад, # ^ |

0

That's partly why I asked for a segment tree template lol

→ Ответить

»

Red0

12 дней назад, # ^ |

← Rev. 4 →

+1

Bru, you could've just asked me over google chat... I legit have a segment tree template that's very good which uses lazy prop.

lazy prop segtree template

struct SegmentTree {
    struct Node {
        int ans = INF, lazy = 0, l, r;

        void leaf(int val) {
            ans = val;
        }
        void Pull(const Node &a, const Node &b) {
            ans = a.ans+b.ans;
        }
        void Push(int val) {
            lazy += val;
        }
    };

    int n;
    vi a;
    vector<Node> st;

    SegmentTree(int _n) : n(_n), a(n, INF), st(4*n) {
        Build(1, 0, n-1);
    }

    SegmentTree(const vector<int> &_a) : n((int) _a.size()), a(_a), st(4*n) {
        Build(1, 0, n-1);
    }

    void Build(int p, int l, int r) {
        st[p].l = l;
        st[p].r = r;
        if(l == r) {
            st[p].leaf(a[l]);
            return;
        }
        int m = (l+r)/2;
        Build(2*p, l, m);
        Build(2*p+1, m+1, r);
        st[p].Pull(st[2*p], st[2*p+1]);
    }

    void Push(int p) {
        if(st[p].lazy) {
            if(st[p].l != st[p].r) {
                st[2*p].Push(st[p].lazy);
                st[2*p+1].Push(st[p].lazy);
            }
            st[p].ans += (st[p].r-st[p].l+1)*st[p].lazy;
            st[p].lazy = 0;
        }
    }

    Node Query(int p, int i, int j) {
        Push(p);
        if(i > st[p].r || j < st[p].l) return {0, 0, 0, 0};
        if(i <= st[p].l && st[p].r <= j) return st[p];
        //int m = (st[p].l+st[p].r)/2;
        Node ret, ls = Query(2*p, i, j), rs = Query(2*p+1, i, j);
        ret.Pull(ls, rs);
        return ret;
    }

    int Query(int i, int j) {
        return Query(1, i, j).ans;
    }

    //range updates where lp needed
    void Update(int p, int i, int j, int val) {
        Push(p);
        if(i > st[p].r || j < st[p].l) return;
        if(i <= st[p].l && st[p].r <= j) {
            st[p].ans += val;
            Push(p);
            return;
        }
        int m = (st[p].l+st[p].r)/2;
        Update(2*p, i, m, val);
        Update(2*p+1, m+1, j, val);
        st[p].Pull(st[2*p], st[2*p+1]);
    }

    void Update(int i, int j, int val) {
        Update(1, i, j, val);
    }

    //for singular updates where non-lp
    void Set(int p, int i, int x) {
        if(st[p].l == st[p].r) {
            st[p].leaf(x);
            return;
        }
        int m = (st[p].l+st[p].r)/2;
        if(i <= m) Set(2*p, i, x);
        else Set(2*p+1, i, x);
        st[p].Pull(st[2*p], st[2*p+1]);
    }
};

→ Ответить

»

rangerscowboys

12 дней назад, # ^ |

0

I might be wrong, but what can fenwick tree do that segment tree can't do?

→ Ответить

»

Red0

12 дней назад, # ^ |

+1

Anything that's possible to be done w/ fenwick tree can be done w/ segment tree(at least to my knowledge). It's just like what M1ngXu mentioned above: fenwick tree is faster to implement.

→ Ответить

»

second_saturday

12 дней назад, # |

0

This is my lazy propagation segment tree template, I tried to learn it with chatgpt i asked the multiple versions of lazy propagation before finalizing this one, may be you can try that too

lazy_seg_tree

#include <bits/stdc++.h>
using namespace std ;

class T {
public:
    int st, en;
    int value;
    T *left  = nullptr ; 
    T *right = nullptr ;
    int lazy = 0 ;

    T(int st_, int en_){
        this->st = st_ ; 
        this->en = en_ ;
    }
};

class SegmentTree {


public:
    SegmentTree(const vector<int>& arr) {
        root = build(0, arr.size() - 1, arr);
    }
    void update(int l, int r, int del) {
        update(root, l, r, del);
    }

    int query(int l, int r) {
        return query(root, l, r);
    }


private:
    T *root;

    T* build(int st, int en, const vector<int>& arr) 
    { 
        if (st > en) return nullptr;
        
        T* node = new T(st, en);

        if (st == en) 
            node->value = arr[st];
        else {
            int mid = (st + en) / 2;
            node->left = build(st, mid, arr);
            node->right = build(mid + 1, en, arr);
            pull(node);
        }
        return node;
    }

    void update(T* node, int l , int r , int del) 
    {
        push(node);
        if (node == nullptr || l > node->en || r < node->st) {
            return;
        }

        if (l <= node->st && node->en <= r ) 
        {
            node->lazy += del;
            push(node);
        }
        else 
        {
            update(node->left, l, r, del);
            update(node->right, l, r, del);
            pull(node);
        }
    }    

    int query(T* node, int l, int r) 
    {
        push(node);
        if (node == nullptr || l > node->en || r < node->st) {
            return 0;
        }
        if (l <= node->st && node->en <= r) {
            return node->value;
        }

        return query(node->left, l, r) + query(node->right, l, r);
    }


    void push(T* node) {
        if ( node && node->lazy != 0) {

            node->value += node->lazy * (node->en - node->st + 1);

            if (node->left )  node->left->lazy += node->lazy;
            if (node->right) node->right->lazy += node->lazy;

            node->lazy = 0;
        }
    }

    void pull( T * node ){
        node->value = node->left->value + node->right->value ;
    }

};

→ Ответить

№	Пользователь	Рейтинг
1	tourist	3690
2	jiangly	3647
3	Benq	3581
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	Radewoosh	3509
8	ecnerwala	3486
9	jqdai0815	3474
10	gyh20	3447

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
3	adamant	163
4	TheScrasse	159
5	nor	157
6	maroonrk	155
7	-is-this-fft-	152
8	Petr	146
8	orz	146
10	BledDest	145

Блог пользователя rangerscowboys