bhupixb

Segment Tree Using Class

Jan 23rd, 2019
141
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.63 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define P pair < int, int >
  5. #define s second
  6. #define f first
  7. #define pb push_back
  8. #define all(v) v.begin(), v.end()
  9. #define rep(i,a,n) for(int i = a; i <= n; ++i)
  10. #define lb(v, x) lower_bound(all(v), x) - v.begin()
  11. #define up(v, x) upper_bound(all(v), x) - v.begin()
  12. #define fo(i, n) for (int i = 1; i <= n; ++i)
  13.  
  14. const int N = 3e5 + 5;
  15. int a[N];
  16. class seg_tree{
  17. public:
  18. int tree[N<<2];
  19. void build(int l, int r, int node){
  20. if(l == r){
  21. tree[node] = a[l];
  22. return ;
  23. }
  24. int mid = l + r >> 1, lc = node + node, rc = 1 + lc;
  25. build(l, mid, lc);
  26. build(mid + 1, r, rc);
  27. tree[node] = tree[lc] + tree[rc];
  28. }
  29. int query(int l, int r, int ql, int qr, int node){
  30. if(qr < l || r < ql)
  31. return 0;
  32. if(ql <= l and r <= qr){
  33. return tree[node];
  34. }
  35. int mid = l + r >> 1, lc = node + node, rc = 1 + lc;
  36. return (query(l, mid, ql, qr, lc)
  37. + query(mid + 1, r, ql, qr, rc));
  38. }
  39. void update(int l, int r, int pos, int val, int node) {
  40. if(pos < l || r < pos)
  41. return;
  42. if(l == r and l == pos) {
  43. tree[node] = val;
  44. return;
  45. }
  46. int mid = l + r >> 1, lc = node + node, rc = 1 + lc;
  47. update(l, mid, pos, val, lc);
  48. update(mid + 1, r, pos, val, rc);
  49. tree[node] = tree[lc] + tree[rc];
  50. }
  51. };
  52. int main(){
  53. ios_base::sync_with_stdio(NULL);
  54. cin.tie(NULL);
  55. cout.tie(NULL);
  56. seg_tree obj;
  57. int n, q, l, r, k;
  58. cin >> n;
  59. fo(i, n)
  60. cin >> a[i];
  61.  
  62. obj.build(1, n, 1);
  63.  
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  
  70.  
  71. return 0;
  72. }
Add Comment
Please, Sign In to add comment