What to do for query problems?

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Howdy Codeforces!

Recently, while solving previous Codefoces problems, I have seen many query problems. What I mean by query problems are: you are given q queries, like updating and printing something.

This is what I have gathered from query problems: - Arrays can be used for simple query problems. - Prefix sums can sometimes be used for query problems (No Updates Ranged Query) - Sets/Multisets are often used for query problems that need O(logn) operations. - Ordered set is used for some query problems (Point Update Range Query) - Segment tree (with lazy propagation on ranged updates) can be used often for Point Update Range Query, Range Update Point Query, Range Update Range Query.

Of course, although segment tree is a solution for many query problems, it isn't easy to code, especially for specialists like me.

Me personally, I have started to direct myself to thinking set/multiset first, because it seems to often work.

Did I miss any ways to solve query problems? Does anyone have a segment tree template that I can use (with lazy propagation)? Do you all have a different approach to query problems than what I do? What do you all see most often as the solution to query problems?

Thanks!

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]); } };

#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 ; } };

Comments (15)

Write comment?

Red0

7 months ago, # |

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

→ Reply

rangerscowboys

6 months ago, # ^ |

I guess you didn't read it. I included ordered set in my blog.

Curious69

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

NemanjaSo2005

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.

7 months ago, # ^ |

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

maybe you can learn fenwick tree?

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

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.

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

← Rev. 4 →

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

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

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

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

Mr.Whitebird

this is really memory consuming, use integers instead of pointers to improve it. (or dont use integers at all). Dynamic segtrees almost never need lazy propogation so that's a non issue.

actually i know this memory consuming, but the reason i love this implementation is because i dont have to focus multiple variable in arguments of fuctions like QL, QR, NodeL , NodeR and for begginers like me it gets really confusing. so i tried this implementation with node class as seperate so this saves me from commiting mistakes, i dont know much about the dynamic segment tree, i just found this usefull, because its has similarities from Leetcode type of coding format. where everything is in class nicely.

rangerscowboys's blog