fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int N = 1e5 + 5;
  5.  
  6. long long ST[4 * N + 5];
  7. int n, Q;
  8.  
  9. // Truy vấn: A(i) = v
  10. // Hàm cập nhật trên cây ST, cập nhật cây con gốc id quản lý đọan [l, r]
  11. void update(int id, int l, int r, int i, int v) {
  12.     if (i < l || r < i) {
  13.         // i nằm ngoài đoạn [l, r], ta bỏ qua nút i
  14.         return ;
  15.     }
  16.     if (l == r) {
  17.         // Đoạn chỉ gồm 1 phần tử, không có nút con
  18.         ST[id] = v;
  19.         return ;
  20.     }
  21.  
  22.     // Gọi đệ quy để xử lý các nút con của nút id
  23.     int mid = (l + r) / 2;
  24.     update(id*2, l, mid, i, v);
  25.     update(id*2 + 1, mid+1, r, i, v);
  26.  
  27.     // Cập nhật lại giá trị Sum của đoạn [l, r] theo 2 nút con:
  28.  
  29.     ST[id] = (ST[id*2] + ST[id*2 + 1]);
  30. }
  31.  
  32. // Truy vấn: tìm max đoạn [u, v]
  33. // Hàm tìm max các phần tử trên cây ST nằm trong cây con gốc id - quản lý đoạn [l, r]
  34.  
  35. long long get(int id, int l, int r, int u, int v) {
  36.     if (v < l || r < u) {
  37.         // Đoạn [u, v] không giao với đoạn [l, r], ta bỏ qua đoạn này
  38.         return 0;
  39.     }
  40.     if (u <= l && r <= v) {
  41.         // Đoạn [l, r] nằm hoàn toàn trong đoạn [u, v] mà ta đang truy vấn, ta trả lại
  42.         // thông tin lưu ở nút id
  43.         return ST[id];
  44.     }
  45.     int mid = (l + r) / 2;
  46.     // Gọi đệ quy với các con của nút id
  47.     return (get(id*2, l, mid, u, v) + get(id*2 + 1, mid+1, r, u, v));
  48. }
  49.  
  50. int main() {
  51.  
  52.     cin >> n >> Q;
  53.     while (Q -- ) {
  54.         char c;
  55.         cin >> c;
  56.  
  57.         if (c == 'S') {
  58.             int i, v;
  59.             cin >> i >> v;
  60.             update(1, 1, n, i, v);
  61.         }
  62.         else {
  63.             int l, r;
  64.             cin >> l >> r;
  65.             cout << get(1, 1, n, l, r) << endl;
  66.         }
  67.  
  68.     }
  69. }
  70.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/OxdFVC
language:
C++14 (gcc 8.3)
created:
19 hours 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!