[C++/Java/Python] 3 solutions: Sqrt Decomposition, Binary Indexed Tree, Segment Tree
✔️ Solution 1: Sqrt Decomposition✔️ Solution 2: Binary Indexed Tree
In BIT structure, there are 2 basic operations:

addValue(idx, value): Add an amount of valu
**✔️ Solution 1: Sqrt Decomposition**
<iframe src="https://leetcode.com/playground/JK22xPhC/shared" frameBorder="0" width="100%" height="1000"></iframe>
**Complexity**
- Time:
	- Constructor: `O(N)`, where `N` is length of `nums` array
	- update, sumRange: `O(sqrt(N))`
- Space: `O(N)`

---
**✔️ Solution 2: Binary Indexed Tree**
- In **BIT** structure, there are 2 basic operations:
	- `addValue(idx, value)`: Add an amount of `value` into element at index `idx` (1-based indexing), time: `O(logN)`
	- `getSum(idx)`: Get sum in range `[0..idx]` (1-based indexing), time: `O(logN)`
- You can practice to use this structure with following problems:
	- [1649. Create Sorted Array through Instructions](https://leetcode.com/problems/create-sorted-array-through-instructions/)


<iframe src="https://leetcode.com/playground/D5Sd2BSs/shared" frameBorder="0" width="100%" height="700"></iframe>

**Complexity**
- Time:
	- Constructor: `O(NlogN)`, where `N` is length of `nums` array
	- update, sumRange: `O(logN)`
- Space: `O(N)`

---
**✔️ Solution 3: Segment Tree**
<iframe src="https://leetcode.com/playground/ezvTcCcn/shared" frameBorder="0" width="100%" height="1000"></iframe>


**Complexity**
- Time:
	- Constructor: `O(N)`, where `N` is length of `nums` array
	- update, sumRange: `O(logN)`
- Space: `O(N)`
['Binary Indexed Tree', 'Segment Tree']