Persistent Dynamic Segment Tree - YessineJallouli/Competitive-Programming GitHub Wiki

Problem : Given l and r , output xor of k smallest elements (it works with sum also)

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

const int N = 1e5 + 5;

struct node;
extern node* empty_node;
struct node {
    int freq; // frequency of a value
    int xr; // xor of values
    node *l, *r;
    node() {
        freq = 0;
        xr = 0;
        l = this;
        r = this;
    }
    node(int f, int x, node *l = empty_node, node *r = empty_node) {
        freq = f;
        xr = x;
        this->l = l;
        this->r = r;
    }
};

node* empty_node = new node;

node* mrg(node* l, node* r) {
    // you can change xor to sum
    return new node(l->freq + r->freq, (l->xr) ^ (r->xr), l, r);
}

node* insert(node *root, int val, int ns = 0, int ne = 1<<30) {
    if (val > ne || val < ns) {
        return root;
    }
    if (ns == ne) {
        int v1 = root->freq + 1;
        int x = 0;
        if (v1 % 2) {
            x = val;
        }
        return new node(v1, x);
    }
    int md = ns + (ne - ns) / 2;
    node *l = insert(root->l, val, ns, md);
    node *r = insert(root->r, val, md + 1, ne);
    return mrg(l,r);
}

node* roots[N];

int query(node *rtst, node *rten, int k, int ns = 0, int ne = 1<<30) {
    if (ns == ne) {
        // return k*ns if it's sum
        if (k % 2) {
            return ns;
        } else {
            return 0;
        }
    }
    int lsz = rten->l->freq - rtst->l->freq;
    int md = ns + (ne - ns) / 2;
    if (k <= lsz) {
        return query(rtst->l, rten->l, k, ns, md);
    } else {
        int xorr = (rten->l->xr) ^ (rtst->l->xr);
        return xorr ^ query(rtst->r, rten->r, k - lsz, md + 1, ne);
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n,m; cin >> n >> m;
    roots[0] = empty_node;
    int a[n + 1];
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        roots[i] = insert(roots[i - 1], a[i]);
    }
    while (m--) {
        int l, r, k;
        cin >> l >> r >> k;
        k = min(k, r - l + 1);
        cout << query(roots[l - 1], roots[r], k) << '\n';
    }
    return 0;
}

Problems :
https://www.spoj.com/problems/KQUERY/en/
https://codeforces.com/group/YTYmnVxV00/contest/568776/problem/F