Python 线段树求区间覆盖

max_size = 100

class Node( object ):
    def __init__( self ):
        self.left = -1
        self.right = -1
        self.sum_num = 0
    def __str__( self ):
        return ‘[%s,%s,%s]‘%( self.left, self.right, self.sum_num )

tree = [ Node() for i in range( max_size ) ]

def build( index, left, right ):
    tree[index].left, tree[index].right = left, right
    if left == right: return
    mid = ( left + right ) >> 1
    build( index << 1, left, mid )
    build( ( index << 1 ) | 1, mid + 1, right )

def insert( index, x, y ):
    if x > tree[index].right or y < tree[index].left: return
    if x <= tree[index].left <= tree[index].right <= y:
        tree[index].sum_num = tree[index].right - tree[index].left + 1
        return
    
    left_son, right_son = index << 1, ( index << 1 ) | 1
    
    if tree[index] == tree[index].right - tree[index].left + 1: return
    if tree[left_son].sum_num < tree[left_son].right - tree[left_son].left + 1:
        insert( left_son, x, y )
    if tree[right_son].sum_num < tree[right_son].right - tree[right_son].left + 1:
        insert( right_son, x, y )

    tree[index].sum_num = tree[right_son].sum_num + tree[left_son].sum_num

if __name__ == ‘__main__‘:
    build( 1, 1, 10 )
    t = insert
    t( 1, 1, 1 )
    t( 1, 3, 4 )
    t( 1, 4, 5 )
    print tree[1].sum_num

Python 线段树求区间覆盖,布布扣,bubuko.com

Python 线段树求区间覆盖

原文：http://blog.csdn.net/pandora_madara/article/details/20643987