v 0. Pasted by alias as cpp at 2011-02-08 22:36:05 MSK and set expiration to never.

Paste will expire never.

  1. const int N = 1 << 16;
  2.  
  3. struct RSQ
  4. {
  5.     int a[N * 2];
  6.     int Sum(int L, int R)
  7.     {
  8.         int res = 0;
  9.         for (L += N, R += N; L < R; L >>= 1, R >>= 1)
  10.         {
  11.             if (L & 1)
  12.             {
  13.                 res += a[L];
  14.                 L++;
  15.             }
  16.             if (R & 1)
  17.             {
  18.                 R--;
  19.                 res += a[R];
  20.             }
  21.         }
  22.         return res;
  23.     }
  24.     void Add(int x, int dx)
  25.     {
  26.         for (int i = x + N; i; i >>= 1)
  27.             a[i] += dx;
  28.     }
  29. };
  30.  
  31. struct RevRSQ
  32. {
  33.     int a[N * 2];
  34.     void Add(int L, int R, int dx)
  35.     {
  36.         for (L += N, R += N; L < R; L >>= 1, R >>= 1)
  37.         {
  38.             if (L & 1)
  39.             {
  40.                 a[L] += dx;
  41.                 L++;
  42.             }
  43.             if (R & 1)
  44.             {
  45.                 R--;
  46.                 a[R] += dx;
  47.             }
  48.         }
  49.     }
  50.     int Sum(int x)
  51.     {
  52.         int res = 0;
  53.         for (int i = x + N; i; i >>= 1)
  54.             res += a[i];
  55.         return res;
  56.     }
  57. };


Editing is locked.