fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. long long n, q;
  5.  
  6. const int MAXN = 1e5 + 5;
  7. long long segTree[4 * MAXN]; // Mảng cây phân đoạn
  8. int A[MAXN]; 
  9.  
  10. void build(int node, int start, int end) {
  11.     if (start == end) {
  12.         segTree[node] = A[start]; // Gán giá trị từ mảng gốc
  13.     } else {
  14.         int mid = (start + end) / 2;
  15.         build(2 * node, start, mid);
  16.         build(2 * node + 1, mid + 1, end);
  17.         segTree[node] = segTree[2 * node] + segTree[2 * node + 1]; // Gộp tổng
  18.     }
  19. }
  20.  
  21. // Cập nhật A[idx] += value
  22. void update(int node, int start, int end, int idx, int value) {
  23.     if (start == end) {
  24.         segTree[node] += value;
  25.     } else {
  26.         int mid = (start + end) / 2;
  27.         if (idx <= mid) {
  28.             update(2 * node, start, mid, idx, value);
  29.         } else {
  30.             update(2 * node + 1, mid + 1, end, idx, value);
  31.         }
  32.         segTree[node] = segTree[2 * node] + segTree[2 * node + 1];
  33.     }
  34. }
  35.  
  36. // Truy vấn tổng từ L đến R
  37. long long query(int node, int start, int end, int L, int R) {
  38.     if (R < start || end < L) return 0; // Ngoài khoảng truy vấn
  39.     if (L <= start && end <= R) return segTree[node]; // Hoàn toàn nằm trong khoảng
  40.  
  41.     int mid = (start + end) / 2;
  42.     long long leftSum = query(2 * node, start, mid, L, R);
  43.     long long rightSum = query(2 * node + 1, mid + 1, end, L, R);
  44.     return leftSum + rightSum;
  45. }
  46.  
  47. int main() {
  48.     cin >> n >> q;
  49.  
  50.     for (int i = 1; i <= n; i++) {
  51.         cin >> A[i];
  52.     }
  53.  
  54.     build(1, 1, n); // Xây dựng cây phân đoạn
  55.  
  56.     while (q--) {
  57.         int type, x, y;
  58.         cin >> type >> x >> y;
  59.         if (type == 1) {
  60.             update(1, 1, n, x, y); // Cập nhật A[x] += y
  61.         } else {
  62.             cout << query(1, 1, n, x, y) << "\n"; // Truy vấn tổng từ A[x] đến A[y]
  63.         }
  64.     }
  65.     return 0;
  66. }
Success #stdin #stdout 0s 5512KB
comments (?)
stdin
copy 
5 3
1 2 3 3 2
2 2 4
1 4 5
2 3 5
stdout
copy 
8
13
https://ideone.com/wDz0ug
language:
C++14 (gcc 8.3)
created:
1 day 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!