Doveqise

Doveqise

万事皆虚,诸行皆允

P3372 【模板】线段树 1 题解

posted on 2019-09-15 08:05:06 | under 题解 |

python用户表示python也是可以写数据结构的 (逃)
所以为什么python不开大时限
话不多说 下面丢一个python版的线段树 巩固一下python知识

class Segment_Tree:
    def __init__(self, alist):初始化线段树
        self.num = alist[:]
        self.tag = [0]*4*len(self.num)
        self.siz = [0]*4*len(self.num)
        self.data = [0]*4*len(self.num)
        self.n = len(self.num)
        self.build(1, 1, n)

    def ls(self, x):左儿子
        return x << 1

    def rs(self, x):右儿子
        return x << 1 | 1

    def push_up(self, x):
        self.data[x] = self.data[self.ls(x)]+self.data[self.rs(x)]

    def add(self, x, k):
        self.data[x] += k*self.siz[x]
        self.tag[x] += k

    def push_down(self, x):下放标记

        if(self.tag[x] != 0):
            if(self.siz[self.siz[self.ls(x)]] != 0):
                self.add(self.ls(x), self.tag[x])
            if(self.siz[self.siz[self.rs(x)]] != 0):
                self.add(self.rs(x), self.tag[x])
            self.tag[x] = 0

    def build(self, x, l, r):建树
        if(l == r):
            self.siz[x] = 1
            self.data[x] = self.num[l-1]
            return
        mid = (l+r) >> 1
        self.build(self.ls(x), l, mid)
        self.build(self.rs(x), mid+1, r)
        self.push_up(x)
        self.siz[x] = self.siz[self.ls(x)]+self.siz[self.rs(x)]

    def update(self, x, ql, qr, l, r, k):
        if(ql <= l) & (r <= qr):
            self.add(x, k)
            return
        self.push_down(x)
        mid = (l+r) >> 1
        if(ql <= mid):
            self.update(self.ls(x), ql, qr, l, mid, k)
        if(qr > mid):
            self.update(self.rs(x), ql, qr, mid+1, r, k)
        self.push_up(x)

    def query(self, x, ql, qr, l, r):
        res = 0
        if(ql <= l) & (r <= qr):
            return self.data[x]
        self.push_down(x)
        mid = (l+r) >> 1
        if(ql <= mid):
            res += self.query(self.ls(x), ql, qr, l, mid)
        if(qr > mid):
            res += self.query(self.rs(x), ql, qr, mid+1, r)
        return res

n, m = input().split()
n = int(n)
m = int(m)
alist = input().split()
alist = [int(i) for i in alist]
bax = Segment_Tree(alist)
while(m > 0):
    a = input().split()
    if(int(a[0]) == 1):
        bax.update(1, int(a[1]), int(a[2]), 1, n, int(a[3]))
    if(int(a[0]) == 2):
        print(bax.query(1, int(a[1]), int(a[2]), 1, n))
    m = m-1