Guest User

Untitled

a guest
Jun 26th, 2017
79
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. int tree[30000000];
  2.  
  3. inline void update(int node,int i,int j,int pos)
  4. {
  5.     if(pos<i || pos>j) return;
  6.    
  7.     if(i==j) // && pos==i
  8.     {
  9.         tree[node]++;
  10.         return;
  11.     }
  12.    
  13.     update(node<<1,i,(i+j)>>1,pos);
  14.     update((node<<1)+1,((i+j)>>1)+1,j,pos );
  15.    
  16.     tree[node]=tree[node<<1]+tree[(node<<1)+1];
  17. }
  18.  
  19. inline int query(int node,int x,int y,int i,int j)
  20. {
  21.    
  22.     if(j<x || i>y)
  23.         return 0;
  24.    
  25.     if(x>=i && y<=j)
  26.         return tree[node];
  27.    
  28.     return query(node<<1,x,(x+y)>>1,i,j)+query((node<<1)+1,((x+y)>>1)+1,y,i,j);
  29. }
RAW Paste Data