javacoder1's blog

PERSISTENT SEGMENT TREE
By javacoder1, history, 8 years ago, In English

Hey , i was learning persistent segment trees , i got what the concept behind it and now i have to solve problems.I guess people out here might be having some built in templates , can you share yours so that i can see how to efficiently code it as i read that too much pointers can cause TLE.

HOW TO UPDATE RANGES USING LAZY PROPAGATION IN THIS METHOD

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (20)
| Write comment?
»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

But you shouldn't be having any problems with pointers since you're "javacoder" right? :P

And check this link for a tutorial and with sample code too.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, Here an interesting problem : E. The Classic Problem and my solution

i think if you explored the accepted codes you will find what you need.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks , i will definitely look into it.If you have codes using this data structure of perhaps an easy question can you please share?

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you help me in the range updates part?

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by javacoder1 (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I use the code posted here , it doesn't use pointers

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Does someone have a max/min template for 2D fenwick?
If it is possible?

I have for one dimensional case, though I don't really understand it but it is fast :D .Link

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it

Actually too much pointers wont cause TLE, but dynamic allocation would. You can use pointers with static pool of nodes. Here is code for this problem

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

YOUR SHIFT SEEMS TO BE STUCK

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone suggest me more questions prefably on codeforces solved using this method which has not been mentioned?

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution for DQUERY.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to handle range updates in persistent segment trees. Point updates for a particular query means that we have to change only log(n) nodes in path from root to leaf so for q queries space complexity would be n+qlog(n) but for the case of range updates i would keep a lazy value at each node but the problem i am facing is that the node to be updated would be representing some range so to change it would mean recreating the whole structure beneath it which be be too much costly considering the fact that there might be more range updates in the queries.Can someone suggest how to implement this?

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

PLease help me , i am stuck

→ Reply
»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Can someone explain how to update ranges in a persistent segment tree?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have one for you. This is a solution of problem HORRIBLE of SPOJ which uses lazy propagation and persistent segment tree.

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

struct node {
    ll value;
    ll lazy;
    node *l, *r;
    node() {
        value = lazy = 0;
        l = r = NULL;
    }
};

void lazy(node *&t, ll l, ll r) {
    if (t->lazy != 0) {
        t->value += t->lazy * (r - l + 1);
        // if t is not a leaf
        if (l < r) {
            if (t->l == NULL) t->l = new node();
            if (t->r == NULL) t->r = new node();
            t->l->lazy += t->lazy;
            t->r->lazy += t->lazy;
        }
        t->lazy = 0;
    }
}

void update(node *&t, ll l, ll r, int x, int y, ll v) {
    // if t == NULL then t hasn't been visited and hasn't been passed any lazy value
    if (t == NULL) t = new node();
    else lazy(t, l, r);
    if (l > y || r < x) return;
    if (l >= x && r <= y) {
        t->value += v * (r - l + 1);
        if (l < r) {
            if (t->l == NULL) t->l = new node();
            if (t->r == NULL) t->r = new node();
            t->l->lazy += v;
            t->r->lazy += v;
        }
        return;
    }
    int m = (l + r) >> 1;
    update(t->l, l, m, x, y, v);
    update(t->r, m + 1, r, x, y, v);
    t->value = t->l->value + t->r->value;
}

ll get(node *t, int l, int r, int x, int y) {
    if (t == NULL) return 0;
    lazy(t, l, r);
    if (l > y || r < x) return 0;
    if (l >= x && r <= y) return t->value;
    int m = (l + r) >> 1;
    return get(t->l, l, m, x, y) + get(t->r, m + 1, r, x, y);
}

// free memory
void del(node *&t) {
    if (t == NULL) return;
    del(t->l);
    del(t->r);
    delete t;
}

int main() {
    int test;
    scanf("%d", &test);
    while (test--) {
        node *t = NULL;
        int n, c;
        scanf("%d %d", &n, &c);
        while (c--) {
            int i;
            scanf("%d", &i);
            if (i == 0) {
                int p, q, v;
                scanf("%d %d %d", &p, &q, &v);
                update(t, 1, n, p, q, v);
            } else {
                int p, q;
                scanf("%d %d", &p, &q);
                printf("%lld\n", get(t, 1, n, p, q));
            }
        }
        del(t);
    }
}
→ Reply