Try Again

基础知识学习
随笔 - 4, 文章 - 0, 评论 - 0, 引用 - 0
数据加载中……

树状数组

class TreeArray
{
    
int c[1100000]; // element id must start at 1
    int size;
    
int lowbit(int x)
    {
        
return x & (-x);
    }
public:
    
void init(int s = N - 1)
    {
        size 
= s;
        memset(c,
0,size * sizeof(c[0]));
    }
    
int sum(int n) // 前n个数的和,包括n
    {
        
int s = 0;
        
while (n > 0)
        {
            s 
+= c[n];
            n 
-= lowbit(n);
        }
        
return s;
    }
    
void plus(int p,int x) // add x to the element at position p
    {
        
while (p <= size)
        {
            c[p] 
+= x;
            p 
+= lowbit(p);
        }
    }
};

posted on 2009-03-13 11:30 NicYun 阅读(211) 评论(0)  编辑 收藏 引用 所属分类: Algorithm


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理