L - 樹狀數組 2

?洛谷 - P3368?

Description

如題，已知一個數列，你需要進行下面兩種操作：

1. 將某區間每一個數加上?x；

2. 求出某一個數的值。

Input

第一行包含兩個整數?N、M，分別表示該數列數字的個數和操作的總個數。

第二行包含?N?個用空格分隔的整數，其中第?i?個數字表示數列第?i?項的初始值。

接下來?M?行每行包含?2?或?4個整數，表示一個操作，具體如下：

操作?1： 格式：1 x y k?含義：將區間?[x,y]內每個數加上?k；

操作?2： 格式：2 x?含義：輸出第?x?個數的值。

Output

輸出包含若干行整數，即為所有操作?22?的結果。

Sample 1

5 5
1 5 4 2 3
1 2 4 2
2 3
1 1 5 -1
1 3 5 7
2 4

6
10

Hint

樣例 1 解釋：

故輸出結果為 6、10。

數據規模與約定

對于?30%的數據：N≤8，M≤10；

對于?70%的數據：N≤10000，M≤10000；

對于?100%?的數據：1≤N,M≤500000，1≤x,y≤n，保證任意時刻序列中任意元素的絕對值都不大于?230。

思路：

問題分析

需要處理兩種操作：

1. 區間增量操作：給區間[x, y]內的每個元素加上k。
2. 單點查詢操作：查詢第x個元素的值。

直接使用暴力方法（遍歷區間進行增量）的時間復雜度為O(N)，對于大規模數據（如N=500000）會導致超時。因此需要使用更高效的數據結構或算法。

差分數組與樹狀數組優化

差分數組可以有效處理區間增量操作，樹狀數組（Fenwick Tree）可以高效實現差分數組的前綴和查詢。

差分數組原理：

• 原數組A的差分數組D定義為D[1] = A[1]，D[i] = A[i] - A[i-1]（i > 1）。
• 區間增量操作[x, y]加上k，只需執行D[x] += k和D[y+1] -= k。
• 查詢A[x]的值即為差分數組D的前綴和sum(D[1..x])。

樹狀數組優化：

• 樹狀數組支持高效的單點更新和前綴查詢（O(logN)時間復雜度）。
• 用樹狀數組維護差分數組D，可以快速處理區間增量和單點查詢。

代碼實現思路

1. 初始化差分數組：

   • 讀取初始數組并構建差分數組D，D[i] = A[i] - A[i-1]（i > 1），D[1] = A[1]。
   • 使用樹狀數組維護D的數值。

2. 處理操作：

   • 區間增量操作1 x y k：調用add(x, k)和add(y+1, -k)。
   • 單點查詢操作2 x：調用count(x)獲取前綴和，即A[x]的值。

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int n, m;
int a[500005];
int lowbit(int x) {return x & (-x);
}
void add(int i, int w) {while (i <= n) {a[i] += w;i += lowbit(i);}
}
可以不寫add中-w就OK了
//void sub(int i, int w) {
//    while (i <= n) {
//        a[i] -= w;
//        i += lowbit(i);
//    }
//}
int count(int i) {int result = 0;while (i > 0) {result += a[i];i -= lowbit(i);}return result;
}
int main() {ios::sync_with_stdio(false);        // 禁用同步cin.tie(nullptr);                   // 解除cin與cout綁定cin >> n >> m;int w;int u;for (int i = 1; i <= n; i++) {cin >> w;if (i == 1) {u = w;add(i, u);}elseadd(i, w-u);u = w;}int h, x,y, k;for (int i = 1; i <= m; i++) {cin >> h;if (h == 1) {cin >> x >> y >> k;add(x, k);add(y + 1, -k);}else {cin >> x;cout << count(x) << endl;}}return 0;
}