# Leetcode 解題記錄 3525. Find X Value of Array II
### 題目大意:
給定一組int array，以及一些queries，每個query都有四個值`[index, value, start, x]`，會將array第`index`的數值改成`value`，求所有從`start`開始且乘積為x的子串數量。以上操作都是modulo一個給定的int k。
### 解法思路: [[code](https://github.com/zBING-QIAN/CodingPractice/blob/main/Leetcode_Record/P_3525.cpp)]
從題目中大概可以看出是要搞range queries, BIT或Fenwick Tree之類的，但是難搞的部分就是range query的目標不是很直覺可以維護的，根據不同的開始位置就必須維護不同的Fenwick Tree，顯然是不會過的，更何況要update array的值，但這邊似乎也算是給個暗示，畢竟能做range update的操作選項也不多，肯定有甚麼東西要用fake segment tree去維護，最直覺的就是去維護區間的product，至此似乎還差一步，把兩個概念合併起來。

所以假設有一個結構可以`O(logn)`搜索/維護區間乘積，再觀察一下題目的限制，k最大只有5，也就是說可以將所有的餘數狀態個別存下來(一個餘數一個Fenwick Tree)，再再觀察一下，假設`k=5`，如果已經維護了每種子串乘積在`[l,r]`間有多少個，現在要求`start`開始結尾在`[l,r]`之間且乘積為4的子串數量，且`start<l`，`[start,l-1]`的乘積假設為3，`(3*3)%5=4(mod 5)`，所以[l,r]之間乘積為3的總數就會是這次query要的，所以要query的過程不同區間取的餘數會會不一樣，取決於[start,l-1]的乘積，蛋蛋蛋蛋蛋蛋蛋但是更新Fenwick Tree會很麻煩，因為一般用Fenwick Tree的range query是先求[0,r]再求[0,l-1]，再相減得到[l,r]的區間值，但是這樣必須對不需要的前綴逆操作，然而逆操作不一定總是存在(例如:0)，所以會無法推估餘數是從哪個餘數轉移回來的，硬是要使用的話要先將array翻轉才能處理要繞很大一圈，但是我就是個狒狒沒想到要如何一起處理，所以搞了醜醜的解法，且複雜度是`O(n(logn)^2)`。最簡單的方式是搭配fake segment tree一起維護區間乘積，許多題解都是用這種方式，且複雜度為`O(nlogn)`。

    void dp_update(vector<vector<int>> &dp,vector<int>&tree,int pos,int v,int k,int n,int ts){
        vector<int> buf = dp[pos];
        int bup = pos+(pos&-pos),bdown = pos-(pos&-pos);
        while(bup<n){
        // 先向下算出要扣多少，假設 1001011(二進位)要更新，向上要去處理的是 1001100，但是
        // [1001010,1001100]的區間如果不往下找會看不到，所以要往下補足該扣的值
            while(bdown&&((bdown&-bdown))<(bup&-bup)){
                int interval = tree_query(tree,bdown,pos-1,ts,k);
                for(int i=0;i<k;i++){
                    buf[(interval*i)%k]+=dp[bdown][i];
                }
                bdown -= (bdown&-bdown);
            }
            int interval = (pos+1==bup)?1:tree_query(tree,pos+1,bup-1,ts,k);
            for(int i=0;i<k;i++){
                dp[bup][(interval*i*tree[ts+pos])%k]-=buf[i];
            }
            for(int i=0;i<k;i++){
                dp[bup][(interval*i*v)%k]+=buf[i];
            }
            bup += (bup&-bup);
        }
        tree_update(tree,pos,v,ts,k);
    }
    

`dp_update`是用Fenwick Tree去維護不同餘數子串個數。
`dp_update`比較複雜，因為向上更新Fenwick Tree前要先扣掉更新前的值所以要有一個向下尋找的操作，這邊是和一般Fenwick Tree不一樣的地方。

### Murmur
這題真的有點難度，一開始沒觀察出來真的想到破頭。後面又因為我自己沒觀察仔細搞了個很複雜的Fenwick Tree update真的弄得很痛苦，特別紀錄一下耍寶的過程。
這題的麻煩點是更新會影響後面的結構，如果用fake segment tree則各自區間維護就可以了不會影響到其他地方，但是Fenwick Tree為了壓縮記憶體空間，將一些連結簡化，更新起來就要去仔細處理簡化掉的結構，總之，如果沒有說很卡記憶體的話，使用fake segment tree會是比較萬用的選擇，雖然code會比較稍微長一點點。