[307] Range Sum Query - Mutable (TBD)

我到底看了什麼捏～這個好難喔 QQ

看完以後覺得好像有點懂，但是不想寫它 XD

https://yuanchieh.page/posts/2022/2022-05-23-%E7%AE%97%E6%B3%95segment-tree-%E8%88%87-binary-indexed-tree-%E8%A7%A3%E9%A1%8C%E6%95%B4%E7%90%86/

原本的暴力解超時了，以為用prefix sum 可以處理，結果一樣超時XD （笑自己）

才發現原來有個時髦的玩意兒叫做 binary index tree (BIT) 跟segment tree 

到底是什麼，也太麻煩了吧！！！時間有限，先放棄好了QQ

超時的prefix sum 版本

typedef struct {

int *nums;

int size;

int *prefix;

} NumArray;

NumArray* numArrayCreate(int* nums, int numsSize) {

NumArray* obj = calloc (1,sizeof (NumArray));

obj->nums = calloc (numsSize, sizeof(int));

obj->size = numsSize;

obj->prefix = calloc (numsSize, sizeof(int));

obj->prefix[0]= nums[0];

for (int i=0; i< numsSize; i++)

{

obj->nums[i]= nums[i];

if (i>0)

obj->prefix[i]= obj->prefix[i-1]+nums[i];

}

return obj;

}

void numArrayUpdate(NumArray* obj, int index, int val) {

obj->prefix[index] = obj->prefix[index] - obj->nums[index]+ val;

obj->nums[index] = val;

for (int i= index; i< obj->size -1; i++)

{

obj->prefix[i+1]= obj->prefix[i]+ obj->nums[i+1];

}

return;

}

int numArraySumRange(NumArray* obj, int left, int right) {

int ret = 0;

if (left==0)

return obj->prefix[right];

ret = obj->prefix[right]- obj->prefix[left-1];

return ret;

}

void numArrayFree(NumArray* obj) {

free (obj->nums);

free(obj);

return;

}

/**

* Your NumArray struct will be instantiated and called as such:

* NumArray* obj = numArrayCreate(nums, numsSize);

* numArrayUpdate(obj, index, val);

* int param_2 = numArraySumRange(obj, left, right);

* numArrayFree(obj);

*/