data-structures - クエリと更新を使用して mod sum を効率的に計算するにはどうすればよいですか

Question

配列 A(A[1..n]={1,2,3} など) が与えられた場合、次の 2 つのクエリが必要です。

1) Update(idx,val) : A[idx]=val の値を更新

2) intクエリ(MOD).....

int Query(int MOD)  :   // say MOD =2 , so 1%2 +2%2 + 3%2 =2
    int ans=0;
    for i=1 to i=n
        ans+=(A[i]%MOD);
    return ans;

MOD のすべての可能な値としてインデックスを持つフェンウィック ツリーを考えましたが、問題は、A[i]%MOD が A[i] ごとに異なる可能性があるため、一定の更新がないことです。効率的に行うにはどうすればよいですか？