fork(1) download 
  1. // iostream is too mainstream
  2. #include <cstdio>
  3. // bitch please
  4. #include <iostream>
  5. #include <vector>
  6. #include <set>
  7. #include <map>
  8. #include <string>
  9. #include <queue>
  10. #include <stack>
  11. #include <algorithm>
  12. #define dibs reserve
  13. #define OVER9000 1234567890
  14. #define tisic 47
  15. #define soclose 10e-7
  16. // mylittlepony
  17. using namespace std;
  18.  
  19. struct IT {
  20.     // uses [a,b) intervals
  21.     struct node {
  22.         int zac,kon,val;
  23.         int son[2];}
  24.     n0; // null node
  25.     vector<node> T; // dat structure
  26.  
  27.     void constT(int akt) { // construct interval tree with root akt
  28.         node n =T[akt];
  29.         if(n.zac+1 == n.kon) return; // this node is leaf, interval [a,a)
  30.         // split the interval in half, construct subtrees for each half
  31.         for(int i =0; i < 2; i++) {
  32.             T[akt].son[i] =T.size();
  33.             if(i == 0) n.kon =(T[akt].zac+T[akt].kon)/2;
  34.             else {
  35.                 n.zac =n.kon;
  36.                 n.kon =T[akt].kon;}
  37.             T.push_back(n);
  38.             constT(T[akt].son[i]);}
  39.         }
  40.  
  41.     IT(int N) { // constructor; T is the interval [0,N)
  42.         n0.zac =n0.val =0;
  43.         n0.kon =N;
  44.         n0.son[0] =n0.son[1] =-1;
  45.         T.push_back(n0);
  46.         constT(0);}
  47.  
  48.     int get(int akt, int pos) { // get value at position pos
  49.         node n =T[akt];
  50.         if(n.zac == pos && n.kon == pos+1) return n.val; // leaf corresponding to pos
  51.         if((n.zac+n.kon)/2 > pos) return get(n.son[0],pos); // pos is in left half
  52.         else return get(n.son[1],pos);} // pos is in right half
  53.  
  54.     void add(int akt, int pos, int v) { // value[pos] +=v
  55.         node n =T[akt];
  56.         T[akt].val +=v;
  57.         if(zac+1 == kon) return; // leaf, can't go any deeper
  58.         // move to the half-interval containing position pos, update it
  59.         if((n.zac+n.kon)/2 > pos) add(n.son[0],pos,v); // it's the left one
  60.         else add(n.son[1],pos,v);}; // it's the right one
  61.  
  62. // look at my code
  63. // my code is amazing
Not running #stdin #stdout 0s 0KB
comments (?)
stdin 
10 3
3 3 9 1 3 1 7 8 3 4
1 5
5 8
4 4
stdout 
Standard output is empty
https://ideone.com/a7X9cP
language:
C++14 (gcc 8.3)
created:
11 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!