Need help for Segment Tree

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

Автор du84n0v, история, 13 месяцев назад, По-английски

Hello everyone. I started to learn segment tree and i choose codeforces EDU section's Segment Tree problems. I need help for (https://codeforces.me/edu/course/2/lesson/4/3/practice/contest/274545/problem/E) problem. Here is my solution: https://codeforces.me/edu/course/2/lesson/4/3/practice/contest/274545/submission/338162999

can you help me to fix this.

UPD: fixed. Thanks all.

du84n0v
13 месяцев назад
16

Комментарии (11)

Показать архивные | Написать комментарий?

ink65536

13 месяцев назад, скрыть # |

I can't see the problem, can you post it here?

→ Ответить

du84n0v

13 месяцев назад, скрыть # ^ |

We have array initially filled by zeros. and we have two types of operation:

1 l r v -> add the value v to the segment from l to r [l, r] 2 i -> find the value of the element with index i.

→ Ответить

ink65536

13 месяцев назад, скрыть # ^ |

← Rev. 2 →

Can't see your code. sry plz post it.

→ Ответить

du84n0v

13 месяцев назад, скрыть # ^ |

← Rev. 2 →

vector <int> T;

void add(int v, int l, int r, int id, int val){
    if(l == r){
        T[v] += val;
        return ;
    }
    int m = (l+r)>>1;
    if(m >= id) add(v<<1, l, m, id, val);
    else add(v<<1|1, m+1, r, id, val);
    T[v] = (T[v<<1] + T[v<<1|1]);
}

int get(int v, int l, int r, int id){
    if(l == r) return T[v];
    int m = (l+r)>>1;
    if(m >= id) return get(v<<1, l, m, id);
    else return T[v<<1] + get(v<<1|1, m+1, r, id);
}

void solve(){
    int n, m; cin >> n >> m;
    vector <int> a(n+1);
    T.resize(n<<2);

    while(m --){
        int ch; cin >> ch;
        if(ch == 1){
            int l, r, v; cin >> l >> r >> v;
            add(1, 1, n, l+1, v);
            add(1, 1, n, r+1, -v);
        }
        else {
            int id; cin >> id;
            cout << get(1, 1, n, id+1) << '\n';
        }
    }
}

→ Ответить