daily pastebin goal
92%
SHARE
TWEET

Untitled

a guest Mar 13th, 2018 53 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. struct SegmentTree {
  6.     struct Node {
  7.         int value;
  8.         Node* left;
  9.         Node* right;
  10.  
  11.         Node(int v, Node* l, Node* r) {
  12.             this->value = v;
  13.             this->left = l;
  14.             this->right = r;
  15.         }
  16.  
  17.         Node() {
  18.             this->value = 0;
  19.             this->left = NULL;
  20.             this->right = NULL;
  21.         }
  22.     };
  23.  
  24.     Node root;
  25.  
  26.     int power_2_over(int x) {
  27.          x--;
  28.          for (int p=1; p<32; p<<=1) x |= (x >> p);
  29.          return ++x;
  30.     }
  31.  
  32.     SegmentTree(vector<int> array, size_t size) {
  33.         size = power_2_over(size);
  34.         vector<Node> prev_nodes (size);
  35.         for (size_t i = 0; i < size; i++)
  36.             prev_nodes[i].value = array[i];
  37.         while (prev_nodes.size() > 1) {
  38.             vector<Node> nodes (prev_nodes.size() / 2);
  39.             size_t j = 0;
  40.             for (size_t i = 0; i < prev_nodes.size(); i += 2) {
  41.                 nodes[j].value = prev_nodes[i].value + prev_nodes[i + 1].value;
  42.                 nodes[j].left = &prev_nodes[i];
  43.                 nodes[j].right = &prev_nodes[i + 1];
  44.                 j++;
  45.             }
  46.             prev_nodes = nodes;
  47.         }
  48.         root = prev_nodes[0];
  49.     }
  50.  
  51. };
  52.  
  53.  
  54. int main()
  55. {
  56.     int n;
  57.     cin >> n;
  58.     vector<int> a(n);
  59.     for (size_t i = 0; i < n; i++)
  60.     SegmentTree t(a, n);
  61.     cout << t.root.value;
  62.     return 0;
  63. }
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