[Data Structure] Tree array template – Code [VS] 1080 line segment tree practice And1081 line segment tree practice 2

CODE[VS] 1080: Click to enter the first floor of the magic tower
CODE[VS] 1081: Click to enter the second floor of the magic tower

The tree array is a good thing. The constant is smaller than the line segment tree, and the code is simpler than the line segment tree.

Based on interval addition, magnetic field summation, interval modification, single-point query, single-point modification, interval Query…

About the lowbit array, this is a very magical thing. It is hard to imagine how the first person who thought of dividing the array into this way would think of it.
lowbit[i] is stored It is a certain number, which is the number at the position of the last 1 in its binary system. Obviously, the odd number lowbit == 1

Every time the interval is modified, it is in the lowbit direction, and each query is in the reverse lowbit direction.

For more detailed instructions, please refer to Liu Rujia’s “Introduction to Algorithmic Competition Classics” or other Shenben Blogs

Line segment tree exercises (interval summation, single-point modification)

< pre class="prettyprint">#include #include using namespace std;int n, m; int a[100001]; int lowbit(int x) {return x&(-x); } void update(int x, int num) {while(x <=n) {a[x]+=num; x+=lowbit(x);}} int sum(int x) {int sum=0; while(x>0) {sum+=a[x]; x-=lowbit(x);} return sum;} int main() {int i,j,temp; < span class="hljs-keyword">int a,x,y; scanf(“%d” ,&n); for(i=1;i<=n;i++) { scanf(“%d”,&temp); upda te(i,temp);} scanf(“%d”,&m); for(i=1;i<=m;i++) {scanf< /span>(“%d%d%d”,&a,&x,&y); if( a==1) update(x, y); else printf(“%d
“,sum(y)-sum(x-1 span>));} return 0; }

Line segment tree Exercise 2 (Interval modification, single-point query)

#include #include #include #include #include const int maxn = 100005;using namespace  std;int n,q;int c[maxn];int b[maxn];int lowbit(int x){ return x&(-x);} inline void span> add(int i,int num){ while (i <= n) {c[i] += num; i += lowbit(i); }}inline int sum(int x){ int tot = 0; while(x> 0) { tot += c[x]; x -= lowbit(x);} return tot;}int main(){ scanf("%d",&n); for(int i =1;i <=n;i++) {< span class="hljs-keyword">int x; scanf("%d" ,&x); add(i,x);} scanf("%d",&q); for(int i = 1;i <= q;i++) {int cz; int aa,bb,xx,ii; scanf("%d",&cz); if(cz == 1) {scanf("%d%d%d ",&aa,&bb,&xx); for(int j = aa;j < = bb;j++) {add(j,xx);}} if(cz == 2) {scanf("%d",&ii); printf ("%d
",sum(ii)-sum(ii-1 ));} }return 0;}

JOJO: DIO What are you doing?!
DIO: I won’t play the line segment tree anymore JOJO!

THE END

By Peacefuldoge

http://blog.csdn.net/loi_peacefuldog