二次元IMOS法

二次元IMOS法

の二次元配列に対して、以下のことができる。

• 　　区間作用(構築前のみ)　
• 　構築
• 　　一点取得(構築後のみ)　

ソースコード

class IMOS2:
    def __init__(self,h,w):
        self.h,self.w=h+1,w+1
        self.l=[0]*(self.h*self.w)
    def add(self,i,j,i_,j_,x):      #矩形[(i,j),(i_,j_))に+xを区間作用
        self.l[i*self.w+j]+=x
        self.l[i_*self.w+j_]+=x
        self.l[i*self.w+j_]-=x
        self.l[i_*self.w+j]-=x
    def build(self):                #構築
        for j in range(self.w):
            for i in range(1,self.h):
                self.l[i*self.w+j]+=self.l[(i-1)*self.w+j]
        for i in range(self.h):
            for j in range(1,self.w):
                self.l[i*self.w+j]+=self.l[i*self.w+j-1]
    def get(self,i,j):              #一点取得
        return self.l[i*self.w+j]
    def __str__(self):
        return '\n'.join([str(self.l[i*self.w:(i+1)*self.w]) for i in range(self.h)])


imos=IMOS2(2,2)
print(imos)         #   [0, 0, 0]
                    #   [0, 0, 0]
                    #   [0, 0, 0]

imos.add(0,0,2,2,1)
print(imos)         #   [1, 0, -1]
                    #   [0, 0, 0]
                    #   [-1, 0, 1]

imos.add(0,1,2,2,10)
print(imos)         #   [1, 10, -11]
                    #   [0, 0, 0]
                    #   [-1, -10, 11]

imos.build()
print(imos)         #   [1, 11, 0]
                    #   [1, 11, 0]
                    #   [0, 0, 0]

print(imos.get(0,0))#   1
print(imos.get(1,1))#   11

例題
競プロ典型90問-028

参考
一次元のIMOS法
k-penciler.hatenablog.com