Advertisement
Josif_tepe

Untitled

Feb 13th, 2023
877
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.31 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <set>
  5. #include <cmath>
  6. #include <map>
  7. #include <cstring>
  8. using namespace std;
  9. const int maxn = 2e5 + 10;
  10. int arr[maxn];
  11. long long segment_tree[3 * maxn];
  12.  
  13. void build_tree(int L, int R, int position) {
  14.     if(L == R) {
  15.         segment_tree[position] = arr[L];
  16.     }
  17.     else {
  18.         int middle = (L + R) / 2;
  19.        
  20.         build_tree(L, middle
  21.                    , 2 * position);
  22.         build_tree(middle + 1, R, 2 * position + 1);
  23.        
  24.         segment_tree[position] = segment_tree[2 * position] + segment_tree[2 * position + 1];
  25.     }
  26. }
  27.  
  28. long long query(int L, int R, int position, int i, int j) {
  29.     if(i <= L and R <= j) {
  30.         return segment_tree[position];
  31.     }
  32.     if(R < i or j < L) {
  33.         return 0;
  34.     }
  35.     int middle = (L + R) / 2;
  36.    
  37.     return query(L, middle, 2 * position, i, j) + query(middle + 1, R, 2 * position + 1, i, j);
  38. }
  39. int main() {
  40.     int n, q;
  41.     cin >> n >> q;
  42.    
  43.     for(int i = 0; i < n; i++) {
  44.         cin >> arr[i];
  45.     }
  46.     build_tree(0, n - 1, 1); // building the tree O(N log(N))
  47.  
  48.     for(int i = 0; i < q; i++) {
  49.         int a, b;
  50.         cin >> a >> b;
  51.         a--; b--;
  52.        
  53.         cout << query(0, n - 1, 1, a, b) << endl;
  54.     }
  55.     return 0;
  56. }
  57.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement