fork(1) download
copy 
  1. #include <cstdio>
  2. #include <cmath>
  3. using namespace std;
  4.  
  5. struct SegmentTreeNode {
  6.     int start, end; // this node is responsible for the segment [start...end]
  7.     int total;
  8.  
  9.     void assignLeaf(int value) {
  10.         total = value;
  11.     }
  12.  
  13.     void merge(SegmentTreeNode& left, SegmentTreeNode& right) {
  14.         total = left.total + right.total;
  15.     }
  16.  
  17.     int query() {
  18.         return total;
  19.     }
  20.     int getValue() {
  21.         return total;
  22.     }
  23.  
  24.     // the value of the update is dummy in this case
  25.     void applyUpdate(int value) {
  26.         total = total+value;
  27.     }
  28. };
  29.  
  30. template<class InputType, class UpdateType, class OutputType>
  31. class SegmentTree {
  32.     SegmentTreeNode* nodes;
  33.     int N;
  34.  
  35. public:
  36.     SegmentTree(InputType arr[], int N) {
  37.         this->N = N;
  38.         nodes = new SegmentTreeNode[getSegmentTreeSize(N)];
  39.         buildTree(arr, 1, 0, N-1);
  40.     }
  41.  
  42.     ~SegmentTree() {
  43.         delete[] nodes;
  44.     }
  45.  
  46.     // get the value associated with the segment [start...end]
  47.     OutputType query(int start, int end) {
  48.         SegmentTreeNode result = query(1, start, end);
  49.         return result.query();
  50.     }
  51.  
  52.     // range update: update the range [start...end] by value
  53.     // Exactly what is meant by an update is determined by the
  54.     // problem statement and that logic is captured in segment tree node
  55.     void update(int start, int end, UpdateType value) {
  56.         update(1, start, end, value);
  57.     }
  58.  
  59.     OutputType update(int index, OutputType value) {
  60.     update(1, 0, N-1, index, value);
  61.   }
  62.  
  63.   OutputType getValue(int lo, int hi) {
  64.     SegmentTreeNode result = getValue(1, 0, N-1, lo, hi);
  65.     return result.getValue();
  66.   }
  67.  
  68. private:
  69.     void update(int stIndex, int lo, int hi, int index, OutputType value) {
  70.     if (lo == hi) {
  71.     nodes[stIndex].applyUpdate(value);
  72.     return;
  73.     }
  74.  
  75.     int left = 2 * stIndex, right = left + 1, mid = (lo + hi) / 2;
  76.     if (index <= mid)
  77.       update(left, lo, mid, index, value);
  78.     else
  79.       update(right, mid+1, hi, index, value);
  80.  
  81.     nodes[stIndex].merge(nodes[left], nodes[right]);
  82.   }
  83.  
  84.     void buildTree(InputType arr[], int stIndex, int start, int end) {
  85.         // nodes[stIndex] is responsible for the segment [start...end]
  86.         nodes[stIndex].start = start, nodes[stIndex].end = end;
  87.  
  88.         if (start == end) {
  89.             // a leaf node is responsible for a segment containing only 1 element
  90.             nodes[stIndex].assignLeaf(arr[start]);
  91.             return;
  92.         }
  93.  
  94.         int mid = (start + end) / 2,
  95.             leftChildIndex = 2 * stIndex,
  96.             rightChildIndex = leftChildIndex + 1;
  97.  
  98.         buildTree(arr, leftChildIndex, start, mid);
  99.         buildTree(arr, rightChildIndex, mid + 1, end);
  100.         nodes[stIndex].merge(nodes[leftChildIndex], nodes[rightChildIndex]);
  101.     }
  102.  
  103.     int getSegmentTreeSize(int N) {
  104.         int size = 1;
  105.         for (; size < N; size <<= 1);
  106.         return size << 1;
  107.     }
  108.  
  109.  
  110.     SegmentTreeNode query(int stIndex, int start, int end) {
  111.         if (nodes[stIndex].start == start && nodes[stIndex].end == end)
  112.             return nodes[stIndex];
  113.  
  114.         int mid = (nodes[stIndex].start + nodes[stIndex].end) >> 1,
  115.             leftChildIndex = stIndex << 1,
  116.             rightChildIndex = leftChildIndex + 1;
  117.         SegmentTreeNode result;
  118.  
  119.         if (start > mid)
  120.             result = query(rightChildIndex, start, end);
  121.         else if (end <= mid)
  122.             result = query(leftChildIndex, start, end);
  123.         else {
  124.             SegmentTreeNode leftResult = query(leftChildIndex, start, mid),
  125.                             rightResult = query(rightChildIndex, mid+1, end);
  126.             result.start = leftResult.start;
  127.             result.end = rightResult.end;
  128.             result.merge(leftResult, rightResult);
  129.         }
  130.  
  131.         return result;
  132.     }
  133.  
  134.     void update(int stIndex, int start, int end, UpdateType value) {
  135.         if (start == end) {
  136.             // we are only applying updates on leaf nodes
  137.             nodes[stIndex].applyUpdate(value);
  138.             return;
  139.         }
  140.  
  141.         int mid = (nodes[stIndex].start + nodes[stIndex].end) / 2,
  142.             leftChildIndex = 2 * stIndex,
  143.             rightChildIndex = leftChildIndex + 1;
  144.  
  145.         if (start > mid)
  146.             update(rightChildIndex, start, end, value);
  147.         else if (end <= mid)
  148.             update(leftChildIndex, start, end, value);
  149.         else {
  150.             update(leftChildIndex, start, mid, value);
  151.             update(rightChildIndex, mid+1, end, value);
  152.         }
  153.         nodes[stIndex].merge(nodes[leftChildIndex], nodes[rightChildIndex]);
  154.     }
  155. };
  156.  
  157. int A[100005];
  158.  
  159. int main() {
  160.     int N, Q, i, queryType, a, b,v,t;
  161.     scanf("%d",&t);
  162.     while(t--){
  163.         scanf("%d %d", &N, &Q);
  164.         for (i = 0; i < N; ++i)
  165.             A[i]=0;
  166.         SegmentTree<int,int,int> tree(A, N);
  167.  
  168.         while (Q--) {
  169.             scanf("%d%d%d", &queryType, &a, &b);
  170.             if (queryType == 0){
  171.                 scanf("%d",&v);
  172.                //this works
  173.                 for(int i=a-1;i<=b-1;i++)
  174.                     tree.update(i,v);
  175.                 //this gives wrong answer
  176. //                tree.update(a-1,b-1,v);
  177.             }
  178.             else{
  179.                 printf("%d\n", tree.query(a-1, b-1));
  180.             }
  181.         }
  182.     }
  183.     return 0;
  184. }
  185.  
Success #stdin #stdout 0s 3680KB
comments (?)
stdin
copy 
1
8 6
0 2 4 26
0 4 8 80
0 4 5 20
1 8 8 
0 5 7 14
1 4 8
stdout
copy 
80
508
https://ideone.com/K41G9r
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

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!