SHARE
TWEET

Segment Tree (point-range)

keverman Jan 28th, 2018 72 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. const int N = (1 << 16);
  2. int T[2 * N], n;
  3.  
  4. void build()
  5. {
  6.     for(int i = n - 1; i > 0; i--)
  7.         T[i] = T[i<<1] + T[i<<1|1];
  8. }
  9.  
  10. void modify(int p, int value)
  11. {
  12.     for(T[p += n] = value; p > 1; p >>= 1)
  13.         T[p>>1] = T[p] + T[p^1];
  14. }
  15.  
  16. int query(int l, int r)
  17. {
  18.     int result = 0;
  19.  
  20.     for (l += n, r += n; l < r; l >>= 1, r >>= 1)
  21.     {
  22.         if(l&1) result += T[l++];
  23.         if(r&1) result += T[--r];
  24.     }
  25.  
  26.     return result;
  27. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top