Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define MAX 100007
- using namespace std;
- struct node{
- int val, acum;
- node *l, *r;
- node(){
- val = acum = 0;
- l = r = NULL;
- }
- } *root;
- void add(node* no,int l, int r, int v){
- no->val += (r-l+1)*v;
- no->acum += v;
- }
- void update(node* no, int l, int r, int x, int y, int v){
- if(r < x || y < l) return;
- else if(x <= l && r <= y) add(no, l, r, v);
- else{
- int mid = (l+r)/2;
- no->l = (no->l == NULL)? new node(): no->l;
- no->r = (no->r == NULL)? new node(): no->r;
- add(no->l, l, mid, no->acum);
- add(no->r, mid+1, r,no->acum);
- no->acum = 0;
- update(no->l, l, mid, x, y, v);
- update(no->r, mid+1, r, x, y, v);
- no->val = no->l->val + no->r->val;
- }
- }
- int query(node* no, int l, int r, int x, int y){
- if(r < x || y < l) return 0;
- else if(x <= l && r <= y) return no->val;
- else{
- int mid = (l+r)/2;
- no->l = (no->l == NULL)? new node(): no->l;
- no->r = (no->r == NULL)? new node(): no->r;
- add(no->l, l, mid, no->acum);
- add(no->r, mid+1, r,no->acum);
- no->acum = 0;
- return query(no->l, l, mid, x, y) +
- query(no->r, mid+1, r, x, y);
- }
- }
- int main(){
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement