SHARE
    TWEET
    Araf_12

    Square_Root_Decomposition

    Apr 17th, 2025
    429
    0
    Never
    Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
    C++ 1.15 KB | Source Code | 0 0
    1. #include <iostream>
    2. #include <cmath>
    3. using namespace std;
    4. int main() {
    5. int n, ara[1000], block[1000] = {}, block_size;
    6. cin >> n;
    7. block_size = sqrt(n);
    8. // Input array elements
    9. for (int i = 0; i < n; i++) {
    10. cin >> ara[i];
    11. }
    12. // Calculate the blocks
    13. for (int i = 0; i < n; i++) {
    14. block[i / block_size] += ara[i];
    15. }
    16. cout << "block size: " << block_size << endl;
    17. int q;
    18. cin >> q;
    19. while (q--) {
    20. int op, x, y;
    21. cin >> op >> x >> y;
    22. if (op == 1) {
    23. // Update operation
    24. ara[x] += y;
    25. block[x / block_size] += y;
    26. } else {
    27. // Query operation (range sum)
    28. int sum = 0;
    29. for (int i = x; i <= y; ) {
    30. if (i % block_size == 0 && i + block_size - 1 <= y) {
    31. sum += block[i / block_size];
    32. i += block_size;
    33. } else {
    34. sum += ara[i];
    35. i++;
    36. }
    37. }
    38. cout << sum << endl;
    39. }
    40. }
    41. return 0;
    42. }
    Advertisement
    Add Comment
    Please, Sign In to add comment
    Public Pastes
    We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
    Not a member of Pastebin yet?
    Sign Up, it unlocks many cool features!

    AltStyle によって変換されたページ (->オリジナル) /